用于查找最近邻居的空间划分算法如何工作？

StackOverflow https://stackoverflow.com/questions/1713736

题

为了找到最近的邻居， 空间分区 是算法之一。它是如何工作的？

假设我有一组 2D 点（x 和 y 坐标），并且给定一个点 (a,b)。该算法如何找到最近邻居？

有帮助吗？

解决方案

空间划分实际上是密切相关的算法家族，其分区空间，以便应用程序能够处理的点或多边形更容易。

我想有很多方法来解决你的问题。我不知道你是多么复杂愿意建立自己的解决方案。一个简单的方法可能会建立一个二叉树切割空间分成2部分的所有中间平面之间的划分点。通过细分递归，直到你用完点建立你的树。

搜索最近邻将被优化，因为树的每个遍历缩小了搜索区域。

在一些文献中，它们称之为一个 kd树

其他提示

这两个视频应该有帮助：

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top