Java Algorithms – Finding Closest N Points to Any Arbitrary Point in Two Dimensions

algorithmsindexingjava

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?

Best 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.
Related Topic