How to sort geographic data for quick search

Question

I have some objects that are geolocalized (I have latitude + longitude for each object). My application should display objects located at a distance of 3 kilometers from the GPS position of the mobile device. I have several thousand objects, and they are localized in a large area (for example, several US states, several small countries), which means in my list of objects that I can place in New York and the other in Miami, but I also have there may be objects that are very close (several meters).

My application is currently doing an iterative search. For each object, I calculate the distance with the GPS position, and if the distance is <= 3KM, I keep the object different, I ignore it. This algorithm is not very efficient, and I am looking for an Algorithm that will give better performance.

I assume that there is a way to sort my objects using geocoordination and find nearby objects located around the GPS position faster.

My current idea is to simply calculate the “extreme points” rectangle, North / South / East / West (from 3 km from the GPS position), to limit the search area. Then I will calculate the distance only for the objects inside this window. I think something better can be done, but I don't have this idea ...

Any suggestion would be appreciated ;-) Thank you,

Seb.

Answer 1

It sounds like looking for the nearest neighbor , but not with the maximum number of neighbors (as in kNN), but with the maximum distance threshold.

The general approach is to place objects in a special data structure that allows you to quickly preempt large parts of the search space. However, they are usually made taking into account Euclidean spaces, and not for the spherical (lat / lon-) plane (flow problems). Therefore, you probably need to convert your coordinates to 3d coordinates in a Cartesian system relative to the center of the sphere, before you can use one of the following data structures to efficiently search for your objects:

• Octree
• kd-tree

Answer 2

Other answers regarding spatial indexes are correct, but not necessarily the easiest solution for you.

I would like to consider something simpler: Group objects by country, then by state, region, city and, finally, by several landmarks in dense cities (where you have a lot of objects o).

Then you will need to fulfill only a few queries (check which country I am entering, what state, region, etc.) to limit myself to a very small set of objects without introducing advanced data structures in the mobile application.

Answer 3

One way to do this without a specialized data structure is likely to sort two copies of your data — once in longitude, once in latitude. Everything that binary searches before closing, both on lat and long, is close.

Similarly, you can use the usual treap (fast) or red-black tree (low volatility).

But there are probably advantages to using an r-tree or kd-tree. What I described is perhaps only to avoid new dependencies or to avoid coding the new data structure from scratch.