Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
Given a database of places with Latitude + Longitude locations, such as 40.8120390, -73.4889650, how would I find all locations within a given distance of a specific location?
It doesn't seem very efficient to select all locations from the DB and then go through them one by one, getting the distance from the starting location to see if they are within the specified distance. Is there a good way to narrow down the initially selected locations from the DB? Once I have (or don't?) a narrowed down set of locations, do I still go through them one by one to check the distance, or is there a better way?
The language I do this in doesn't really matter. Thanks!
Answer
Start by Comparing the distance between latitudes. Each degree of latitude is approximately 69 miles (111 kilometers) apart. The range varies (due to the earth's slightly ellipsoid shape) from 68.703 miles (110.567 km) at the equator to 69.407 (111.699 km) at the poles. The distance between two locations will be equal or larger than the distance between their latitudes.
Note that this is not true for longitudes - the length of each degree of longitude is dependent on the latitude. However, if your data is bounded to some area (a single country for example) - you can calculate a minimal and maximal bounds for the longitudes as well.
Continue will a low-accuracy, fast distance calculation that assumes spherical earth:
The great circle distance d between two points with coordinates {lat1,lon1} and {lat2,lon2} is given by:
d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))
A mathematically equivalent formula, which is less subject to rounding error for short distances is:
d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))
d is the distance in radians
distance_km ≈ radius_km * distance_radians ≈ 6371 * d
(6371 km is the average radius of the earth)
This method computational requirements are mimimal. However the result is very accurate for small distances.
Then, if it is in a given distance, more or less, use a more accurate method.
GeographicLib is the most accurate implementation I know, though Vincenty inverse formula may be used as well.
If you are using an RDBMS, set the latitude as the primary key and the longitude as a secondary key. Query for a latitude range, or for a latitude/longitude range, as described above, then calculate the exact distances for the result set.
Note that modern versions of all major RDBMSs support geographical data-types and queries natively.