Octree最近的邻居搜索 [英] Nearest neighbor search in Octree
问题描述
NN算法如何在八叉树上工作？我一直在寻找一个很好的解释，但是大多数时候人们只是说使用KD-tree。我做不到，我需要一步一步地可视化NN算法。
How does a NN algorithm work on an octree? I have searched for a good explanation, but most of the time people just say used KD-tree instead. I cant do it, i need to visualize NN algorithm on octree step-by-step.
我认为最合乎逻辑的方法是：
As i can think the most logical way would be to:
1）查找该点所属的子八分位。
1) Find the sub-octant where the point belongs to.
2）计算到该八分位数最近点的距离
2) Calculate distance to the nearest point in that octant
3）检查是否与
4）如果找到更近的点，则重新计算搜索距离。
4) If a closer point is found, recalculate the search distance.
5 ）重复直到所有可能的八分圆都被遍历
5) Repeat until all possible octants have been traversed
6）返回最接近的点
但是我想不起来
推荐答案
查找最接近搜索点的点或获取列表的列表点按距离增加的顺序排列，可以使用优先级队列，该队列可以同时包含树的点和内部节点，从而可以按距离顺序将它们删除。
To find the point closest to a search point, or to get list of points in order of increasing distance, you can use a priority queue that can hold both points and internal nodes of the tree, which lets you remove them in order of distance.
对于点（叶），距离就是该点到搜索点的距离。对于内部节点（八分圆），该距离是从搜索点到可能在八分圆中的任何点的最小距离。
For points (leaves), the distance is just the distance of the point from the search point. For internal nodes (octants), the distance is the smallest distance from the search point to any point that could possibly be in the octant.
现在，要搜索，您只需将树的根放入优先级队列，然后重复：
Now, to search, you just put the root of the tree in the priority queue, and repeat:
- 删除优先级队列的头部；
- 如果队列的头部是一个点，则它是树中尚未返回的最近点。您知道这一点，因为如果某个内部节点可能有一个更近的点，那么它将首先从优先级队列中返回；
- 如果队列的头是一个内部节点，然后将其子级放回队列中。
这将按与搜索点的距离递增的顺序生成树中的所有点。同样的算法也适用于KD树。
This will produce all the points in the tree in order of increasing distance from the search point. The same algorithm works for KD trees as well.
这篇关于Octree最近的邻居搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
