I have a list of coordinates and I need to find the closest coordinate to a specific point which I'll call P.

At first I tried to just calculate the distance from each coordinate to P, but this is too slow.

I then tried to store these coordinates as a quad-tree, find the leaf node that contains P, then find the closest coordinate in that leaf by comparing distances of every coordinate to P. This gives a good approximation for the closest coordinate, but can be wrong sometimes. (when a coordinate is outside the leaf node, but closer). I've also tried searching through the leaf node's parent, but while that makes the search more accurate, it doesn't make it perfect.

If it is possible for this to be done with a quad-tree, please let me know how, otherwise, what other methods/data structures could I used that are reasonably efficient, or is it even possible to do this perfectly in an efficient manner?

CodePudding user response：

Try "loose quadtree". It does not have a fixed volume per node. So it can adjust each node's bounding volume to adapt to the items added.

If you don't like quadtree's traversing performance and if your objects are just points, adaptive-grid can perform fast or very close to O(N). But memory-wise, loose quadtree would be better.

CodePudding user response：

There is an algorithm by Hjaltason and Samet described in their paper "Distance browsing in spatial databases". It can easily be applied to quadtrees, I have an implementation here.

Basically, you maintain a sorted list of object, the list is sorted by distance (closest first), and the objects are either point in your tree (you call the coordinates) or nodes in the tree (distance to closest corner, or distance=0 if they overlap with you search point). You start adding all nodes that overlap with your search point, and add all points and subnodes in these points. Then you simply return points from the top of the list until you have as many closest points as you want. If a node is at the top of the list, add points/subnodes from that node to the list and check the top of the list again. Repeat.