八叉树中的最近邻搜索

Question

NN 算法如何在八叉树上工作？我已经寻找了一个很好的解释，但大多数时候人们只是说使用 KD-tree 代替。我做不到，我需要一步一步地在八叉树上可视化 NN 算法。

我认为最合乎逻辑的方法是：

1) 找到该点所属的子八分圆。

2）计算到该八分圆中最近点的距离

3）检查与该距离内的相邻八分圆是否有重叠

4) 如果找到更近的点，重新计算搜索距离。

5) 重复直到遍历所有可能的八分圆

6) 返回最近点

但我无法为这个想出一个好的一步一步的可视化。

Answer 1

要找到最接近搜索点的点，或按距离递增的顺序获取点列表，您可以使用优先级队列，该队列可以同时保存点和树的内部节点，这样您就可以按距离顺序删除它们。

对于点（叶子），距离就是点到搜索点的距离。对于内部节点（八分圆），距离是从搜索点到八分圆中可能存在的任何点的最小距离。

现在，要搜索，只需将树的根放入优先级队列，然后重复：

1. 移除优先队列的头部；
2. 如果队列的头部是一个点，那么它就是树中尚未返回的最近点。你知道这一点，因为如果任何内部节点可能有一个更近的点，那么它会首先从优先级队列中返回；
3. 如果队列的头是内部节点，则将其子节点放回队列

这将按与搜索点的距离增加的顺序生成树中的所有点。相同的算法也适用于 KD 树。