5

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

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

4

2 回答 2

4

空间分区实际上是一系列密切相关的算法，它们对空间进行分区，以便应用程序可以更轻松地处理点或多边形。

我认为有很多方法可以解决您的问题。我不知道您愿意构建您的解决方案有多复杂。一种简单的方法可能是构建一棵二叉树，将空间分成 2。所有点都划分在某个中间平面之间。通过递归细分直到用完点来构建树。

然后将优化搜索最近的邻居，因为树的每次遍历都会缩小搜索区域。

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

于 2009-11-11T08:18:52.537 回答
2

这两个视频应该会有所帮助：

于 2011-06-03T12:18:41.913 回答