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

by

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.

More Related Contents:

  1. Calculate distance between two latitude-longitude points? (Haversine formula)
  2. What is the simplest and most robust way to get the user’s current location on Android?
  3. How do I get the current GPS location programmatically in Android?
  4. Simple calculations for working with lat/lon and km distance?
  5. Calculating new longitude, latitude from old + n meters
  6. How to find my distance to a known location in JavaScript
  7. What does O(log n) mean exactly?
  8. Generate an integer that is not among four billion given ones
  9. Find duplicates in an array, without using any extra space
  10. How to generate Sudoku boards with unique solutions
  11. How to round floats to integers while preserving their sum?
  12. Modulus power of big numbers
  13. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  14. Maximize the rectangular area under Histogram
  15. Compute social distance between two users
  16. Efficient algorithm for ordering different types of objects
  17. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  18. How to find two most distant points?
  19. Smooth spectrum for Mandelbrot Set rendering
  20. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  21. Sorting an array with minimal number of comparisons
  22. Determining if two line segments intersect? [duplicate]
  23. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  24. How to find distance from the latitude and longitude of two locations?
  25. Non-Recursive Merge Sort
  26. Reversing CRC32
  27. What is the best way to check the strength of a password?
  28. Algorithm for merging two max heaps?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment