# Finding the closest n points to any arbitrary point in two dimensions (r-tree, quadtree, spatial index)

I have a distribution of two dimensional point objects. How is it possible to find the nearest N number of points to any given point without iterating over the entire collection of points (and only keeping the smallest 'n')? I will be doing this for every point so brute force technique (which i'm using right now. There are 12,000+ points within this set so sometimes premature optimization is the.. mature route to take.

I've looked at R-trees however as far as i'm aware they return all points within a given distance of a point, this could potentially work but i'd need to start at an extremely small distance and make successively larger searches until 'n' are found. Perhaps i'd even need to create a custom geometric circle object and use this to bound the search instead of the default square, thoughts on this approach? Is the circle necessary?

Are quadtrees any better for this? Is it possible to traverse from smallest to largest boxes in search of 5 closest points? It seems this might have potential too -- although i've only taken a cursory glance at this algorithm compared to r-trees.

What's the best way to tackle this accurately without resorting to brute force?

• Commented Apr 14, 2015 at 14:03
• What exactly is your question? It sounds like you have identified 2 good candidate algorithms, and you need to research more and decide between them. Commented Apr 14, 2015 at 14:04
• @MobyDisk - OP is looking for a comparison between the two algorithms and has provided a measure of scale to help evaluate the two algorithms. It seems on-topic enough to me.
– user53019
Commented Apr 14, 2015 at 14:13
• Regarding taking small steps: Don't overly worry about getting too many points. Extra points is often not that bad: if you wanted 5 but got 50, that's okay. Just sort the 50 points by distance. That is a lot less than sorting 12,000 points by distance. If your iterations are too small you will just waste CPU time. It is similar to having a quadtree where you work really hard to have each quad have only 1 point. You will spend more time subdividing than it is worth. Commented Apr 14, 2015 at 14:20
• @MobyDisk thank you. Even writing out the above in plain english instead of crunching information in my brain helped me further understand what I am and am not looking for. You're right about not incrementing too small. Any suggestion in the relative size I should scale compared to the total space (a uniform distribution could be assumed I suppose)? If not I can just run a series of tests on my actual data to find a good size of increase. Commented Apr 14, 2015 at 14:49

## 1 Answer

This is easy.

• Walk down the tree (quad tree or R-Tree, etc) until you find the lowest node that contains the “search point”.
• Then look at the parent of that node, and check all points that is contained within the parent (including sub notes)
• If you have not found enough points, then move on to the parent’s parent etc.

Remember

• That the nearest point may be in a sibling node.
• For more “marks” order the search so that you can bail out as soon as you know that you have the n closet point.
• By keeping a stack of nodes as you search down, you don’t need to store a pointer to the parent in each tree note.
• How you split a node into sub nodes does not change this, hence R-Tree and Quod Tree can be searched in the same way.