如何使用KDTrees实现最近邻居搜索？

Question

所以，我正在实施一个KD-Tree做最近的邻居搜索。我已经建立了树的部分工作，但我不认为我完全理解搜索部分。

关于遍历树以搜索邻居，维基百科的文章说以下内容：

Starting with the root node, the algorithm moves down the tree recursively, in the same 
way that it would if the search point were being inserted (i.e. it goes right or left 
depending on whether the point is greater or less than the current node in the split 
dimension). 

什么是“比吐尺寸当前节点或大或小的意思是我们比较基础的点？在距离查询或我们比较点的分割尺寸？

此外，有人可以解释关于超空间和超平面的部分吗？我觉得我理解它，但因为我不知道我想一些更多解释。

谢谢！

Answer 1

每个节点沿着一个轴将空间拆分成2个半空间。你看看问题所在的位置是否与该分割平面有关，以决定树的哪一侧下降。例如，如果你的观点是（4,7,12），并且你有一个分割平面将y轴切割为9，那么你会比较7和9，并决定沿着左边（小于）首先是kd树。找到左边最近的邻居后，检查它是否接近2（到分割平面的距离：9-7）。如果它比分割平面更近，则不需要遍历另一半树。这就是为什么它工作得很好，大多数时候你只需要遍历一个子树。

希望有所帮助。