Find the nearest geo positions

Question

I am looking for a way to get the nearly geo positions from one geo position. I can calculate the difference from two position, but I need to find all geo positions from a point with a radius of 10-20 miles. I find a similaire on flickr:

http://m.flickr.com/#/nearby/

Anybody an idear how it works? They must convert a latitude and longitude to a unique value and must find all entries nearly this position or something else.

Thanks for help!

Answer 1

Use a (point-)quad tree, or k-d tree, or if the number of points is not high, you even could use a brute force search.
Do not use voronoi diagrams. They are one of the most complex algos to implement.

Answer 2

You can use a kd-Tree. Some time ago I tried this one and it worked quite well:

https://github.com/jmhodges/kdtree2

Answer 3

You might use Voronoi Diagrams, but probably pre-sorting your data by each coordinate (separately) and then finding an intersection of point sets which lay nearby for each of coordinates would solve your problem easier.

A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications.