[algorithm] 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!

What you need is spatial search. You can use Solr Spatial search. It also got lat/long datatype built in, check here.

Since you say that any language is acceptable, the natural choice is PostGIS:

SELECT * FROM places
WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;

If you want to use WGS datum, you should set $spheroid to 'SPHEROID["WGS 84",6378137,298.257223563]'

Assuming that you have indexed places by the geom column, this should be reasonably efficient.

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?"

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;

You may convert latitude-longitude to UTM format which is metric format that may help you to calculate distances. Then you can easily decide if point falls into specific location.

Thanks to the solution provided by @yogihosting I was able to achieve similar result from schemaless columns of mysql with codes shown below:

// @params - will be bound to named query parameters
$criteria = [];
$criteria['latitude'] = '9.0285183';
$criteria['longitude'] = '7.4869546';
$criteria['distance'] = 500;
$criteria['skill'] = 'software developer';

// Get doctrine connection 
$conn = $this->getEntityManager()->getConnection();

        $sql = '
               SELECT DISTINCT m.uuid AS phone, (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) AS distance FROM member_profile AS m 
               INNER JOIN member_card_subscription mcs ON mcs.primary_identity = m.uuid
               WHERE mcs.end > now() AND JSON_SEARCH(m.skill_logic, "one", :skill) IS NOT NULL  AND (((acos(sin((:latitude*pi()/180)) * sin((JSON_EXTRACT(m.location, "$.latitude")*pi()/180))+cos((:latitude*pi()/180)) * 
              cos((JSON_EXTRACT(m.location, "$.latitude")*pi()/180)) * 
              cos(((:longitude - JSON_EXTRACT(m.location, "$.longitude"))*pi()/180))))*180/pi())*60*1.1515*1.609344) <= :distance ORDER BY distance
               ';
        $stmt = $conn->prepare($sql);
        $stmt->execute(['latitude'=>$criteria['latitude'], 'longitude'=>$criteria['longitude'], 'skill'=>$criteria['skill'], 'distance'=>$criteria['distance']]);
        var_dump($stmt->fetchAll());

Please note the above code snippet is using doctrine DB connection and PHP

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

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

You may find these questions helpful:

• Formulas to Calculate Geo Proximity
• Maximum length of a decimal latitude/longitude Degree?

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.

you may check this equation i think it will help

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;