Finding the closest point to a given point

Question

Hello- I have searched all over for this, but I can't seem to find the best approach to this. I have about 22000 lat/lon points and I want to find the closest one's to the current location of the iPhone. I've seen people ask about Quad Trees, Dijkstra's Algorithm, and spatial databases. Which is the best for the iPhone? Spatial databases seem easiest, but I am not sure.

EDIT: there are actually over 20,000 points. You think iterating through all of them is the way to do it? But thanks for you input.

Thanks.

Answer 1

Why is this complicated? Iterate through the 2000 points taking x distance squared plus y distance squared for each point. The smallest resulting value is your closest point. O(N)

Answer 2

Actually, it is best to use Haversine (great circle) calculation for Lat/Long points, otherwise increasingly large distances will be wrong, especially if you use simple trig like in Jherico's answer.

A quick search provides this javascript example:

var R = 6371; // km Radius of earth
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

In terms of the datastructure, Geohash is worth looking at.

Answer 3

As you are on iPhone, you can use CoreLoaction to perform the geographic distance - using CLLocation's – getDistanceFrom:

I would be tempted to use a brute force linear search though all 2k points nad, if that isn't fast enough, switch to something like GeoHash to store meta data against your points for search.

Answer 4

If you need better than O(N), you can only get that if you first pay N lg N for building a spatial hash of some sort (a quadtree, octree, hash grid, or similar). Then each test will be approximately O(lg N), and can be much better typically by caching the last location you checked, if there's a lot of coherency (generally, there is).

I would probably build an octree in Euler (geocentric, XYZ) space, because that allows me to get "true" distance, not "warped" lat/lon distance. However, in practice, a quad tree in lat/lon space will probably work well enough. Once you have a hit, you hold on to that tree node (assuming the tree isn't re-built at runtime), and the next query starts walking from that tree node, and only needs to worry about nodes that may be closer if the previous point moved further away from the previous answer.

Answer 5

Why not tile the globe into regions? (Think hexes.) Then, either when you add points to your list, or in one big pre-processing loop, for each point, store the region it is.

Then, when searching for points near point A in hex X, you only need to check points in hex X and a maximum of 3 neighbouring hexes.

If this is still too many points to check, add subregions.

Answer 6

I think this algorithm works:

Create an array sorted by latitude Create an array sorted by longitude

To find the closest, first find the closest by latitude by doing a binary search in the latitude array. Do the same for the longitude array. Now you have 2 points, one closest by latitude, the other closest by longitude. Compute the distances to each point via the pythagorean theorem. The closest point wins.

Roger