Nearest neighbor search in Octree

Question

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) Find the sub-octant where the point belongs to.

2) Calculate distance to the nearest point in that octant

3) Check if there is any overlap with neighboring octants within that distance

4) If a closer point is found, recalculate the search distance.

5) Repeat until all possible octants have been traversed

6) Return the closest point

But i cant think up a good step by step visualization for this one.

Answer 1

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:

1. Remove the head of the priority queue;
2. If the head of the queue was a point, then it is the closest point in the tree that you have not yet returned. You know this, because if any internal node could possibly have a closer point, then it would have been returned first from the priority queue;
3. If the head of the queue was an internal node, then put its children back into the queue

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.