八叉树中的最近邻搜索

Question

NN算法如何在八叉树上运行？我已经搜索了好多资料，但大多数人都只是说用KD树代替。我需要逐步可视化八叉树上的NN算法。

我认为最合理的方法是：

1）找到点所属的子八叉树。

2）计算该八叉树中最近点的距离。

3）检查是否存在与该距离内相邻八叉树的重叠部分。

4）如果发现更近的点，则重新计算搜索距离。

5）重复以上步骤，直到遍历所有可能的八叉树。

6）返回最近的点。

但我无法想出一个好的逐步可视化方法。

- Marko Taht

Answer 1

要找到距离搜索点最近的点，或者按照递增的距离顺序获取点的列表，您可以使用一个优先队列，该队列可以容纳树的节点和内部节点，从而让您按照距离的顺序移除它们。

对于点（叶子），距离只是该点与搜索点之间的距离。对于内部节点（八分之一），距离是从搜索点到可能在八分之一中的任何点的最小距离。

现在，要进行搜索，只需将树的根放入优先队列中，并重复以下步骤：

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

这将按照距离递增的顺序产生树中所有点的结果。相同的算法也适用于KD树。

- Matt Timmermans