Finding the closest point to a given point

Question

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

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.