I need to write a program that does the following:
- Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places
- Store them in a data structure once
- Provide a "nearby" lookup function that can efficiently return the N closest objects for a given lat/long
Currently, I'm doing the following, which is suboptimal:
- Store all objects in a hash, with array keys like
- At search time, find all objects in an arbitrary-sized circle around the target. Eg, if the search is at
[0,0], I can get all objects within 1 degree by pulling
- Order the found objects by actual distance to the target and take the top N
This is obviously inefficient, because often there are many more matches than N.
One improvement could be to examine locations in concentric squares outward from the center: all points 0 degrees from the center, all points 1 degree from the center, 2 degrees, etc, and stop after the first square when I have at least the number of objects needed. Then I could sort those by actual, fine-grained distance and take the top N.
Is there some well-established way of doing this search efficiently?