有关查找最近的邻居，空间划分是的算法。它是如何工作的？

For finding the nearest neighbor, Space Partitioning is one of the algorithms. How does it work?

假设我有一个2D设定点（x和y坐标），而我给了点（A，B）。如何将这个算法找出最近的邻居？

Suppose I have a 2D set of points (x and y coordinates), and I am given a point (a,b). How would this algorithm find out the nearest neighbor?

推荐答案

空间分划分实际上是一个家庭密切相关的算法，该分区的空间，使应用程序可以处理点或多边形更容易。

Spacial partitioning is actually a family of closely related algorithms that partition space so that applications can process the points or polygons easier.

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

I reckon there are many ways to solve your problem. I don't know how complex you are willing to build your solution. A simple way would probably to build a binary tree cutting the space into 2. All the points divided between some middle plane. Build your tree by subdividing recursively until you run out of points.

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

Searching for the nearest neighbor will then be optimized, because each traversal of the tree narrows down the search area.

在一些文献中，他们称这是一个 kd树

In some literature, they call this a kd tree