Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location

Question

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!

Solution 1

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.

Solution 2

Based on the current user's latitude, longitude and the distance you wants to find,the sql query is given below.

SELECT * FROM(
    SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t
WHERE distance <= @distance

@latitude and @longitude are the latitude and longitude of the point. Latitude and longitude are the columns of distances table. Value of pi is 22/7

Solution 3

Tank´s Yogihosting

I have in my database one goups of tables from Open Streep Maps and I tested successful.

Distance work fine in meters.

SET @orig_lat=-8.116137;
SET @orig_lon=-34.897488;
SET @dist=1000;

SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;

Solution 4

PostgreSQL GIS extensions might be helpful - as in, it may already implement much of the functionality you are thinking of implementing.

Solution 5

As biziclop mentioned, some sort of metric space tree would probably be your best option. I have experience using kd-trees and quad trees to do these sorts of range queries and they're amazingly fast; they're also not that hard to write. I'd suggest looking into one of these structures, as they also let you answer other interesting questions like "what's the closest point in my data set to this other point?"

View more solutions