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

User · Answer

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  lt   dist ORDER BY distance ASC LIMIT 100

User · Answer

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  lt    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

User · 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

User · Answer

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

User · Answer

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

User · Answer

Since you say that any language is acceptable  the natural choice is PostGIS    SELECT   FROM places WHERE ST DistanceSpheroid geom   location   spheroid   lt   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

User · Answer

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  lt  25 ORDER BY distance LIMIT 0   20

User · Answer

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

User · Answer

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- gt getEntityManager  - gt 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  gt  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   lt    distance ORDER BY distance                            stmt    conn- gt prepare  sql            stmt- gt execute   latitude   gt  criteria  latitude     longitude   gt  criteria  longitude     skill   gt  criteria  skill     distance   gt  criteria  distance              var dump  stmt- gt fetchAll       Please note the above code snippet is using doctrine DB connection and PHP

User · Answer

You may find these questions helpful    Formulas to Calculate Geo Proximity Maximum length of a decimal latitude longitude Degree

User · Answer

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

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

Examples related to algorithm

Examples related to geolocation

Examples related to gps

Examples related to location

Examples related to latitude-longitude