NN算法如何在八叉树上工作？我搜索了一个很好的解释，但大多数时候人们只是说使用了KD树 . 我不能这样做，我需要逐步在八叉树上可视化NN算法 .
我认为最合乎逻辑的方式是：
1）找到该点所属的子八分圆 .
2）计算到该八分圆中最近点的距离
3）检查该距离内是否与相邻的八分圆重叠
4）如果找到更近的点，则重新计算搜索距离 .
5）重复直到遍历所有可能的八分圆
6）返回最近的点
但我不能为这一步想出一个好的一步一步的可视化 .
要查找最接近搜索点的点，或按距离增加的顺序获取点列表，可以使用可以保存树的两个点和内部节点的优先级队列，这样可以按距离的顺序删除它们 .
对于点（叶子），距离只是点与搜索点的距离 . 对于内部节点（八分圆），距离是从搜索点到可能在八分圆中的任何点的最小距离 .
现在，要搜索，只需将树的根放在优先级队列中，然后重复：
删除优先级队列的头部;
如果队列的头部是一个点，那么它是您尚未返回的树中最近的点 . 你知道这一点，因为如果任何内部节点可能有一个更近的点，那么它将首先从优先级队列返回;
如果队列的头部是内部节点，则将其子节点放回队列中
这将按照距搜索点的距离增加的顺序生成树中的所有点 . 相同的算法也适用于KD树 .
1 回答
要查找最接近搜索点的点，或按距离增加的顺序获取点列表，可以使用可以保存树的两个点和内部节点的优先级队列，这样可以按距离的顺序删除它们 .
对于点（叶子），距离只是点与搜索点的距离 . 对于内部节点（八分圆），距离是从搜索点到可能在八分圆中的任何点的最小距离 .
现在，要搜索，只需将树的根放在优先级队列中，然后重复：
删除优先级队列的头部;
如果队列的头部是一个点，那么它是您尚未返回的树中最近的点 . 你知道这一点，因为如果任何内部节点可能有一个更近的点，那么它将首先从优先级队列返回;
如果队列的头部是内部节点，则将其子节点放回队列中
这将按照距搜索点的距离增加的顺序生成树中的所有点 . 相同的算法也适用于KD树 .