Geo Proximity Search: The Haversine Equation

I’m working on a project that requires Geo proximity search. Basically, what I’m doing is plotting a radius around a point on a map, which is defined by the distance between two points on the map given their latitudes and longitudes. To achieve this I’m using the Haversine formula (spherical trigonometry). This equation is important in navigation, it gives great-circle distances between two points on a sphere from their longitudes and latitudes. You can see it in action here: Radius From UK Postcode.

This has already been covered in some blogs, however, I found most of the information to be inaccurate and, in some cases, incorrect. The Haversine equation is very straight forward, so there’s no need to complicate things.

I’ve implemented the solution in SQL, Python and PHP. Use the one that suits you best.

SQL implementation

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

Python implementation

from __future__ import division
import math

longitude = float(-2.708077)
latitude = float(53.754842)
radius = 20

lng_min = longitude - radius / abs(math.cos(math.radians(latitude)) * 69)
lng_max = longitude + radius / abs(math.cos(math.radians(latitude)) * 69)
lat_min = latitude - (radius / 69)
lat_max = latitude + (radius / 69)

print 'lng (min/max): %f %f' % (lng_min, lng_max)
print 'lat (min/max): %f %f' % (lat_min, lat_max)

PHP implementation

$longitude = (float) -2.708077;
$latitude = (float) 53.754842;
$radius = 20; // in miles

$lng_min = $longitude - $radius / abs(cos(deg2rad($latitude)) * 69);
$lng_max = $longitude + $radius / abs(cos(deg2rad($latitude)) * 69);
$lat_min = $latitude - ($radius / 69);
$lat_max = $latitude + ($radius / 69);

echo 'lng (min/max): ' . $lng_min . '/' . $lng_max . PHP_EOL;
echo 'lat (min/max): ' . $lat_min . '/' . $lat_max;

It outputs the same result:

lng (min/max): -3.1983251898421/-2.2178288101579
lat (min/max): 53.464986927536/54.044697072464

Happy Geolocating!

27 responses to “Geo Proximity Search: The Haversine Equation”

  1. Hi Federico,

    Yes you are correct, in my example script the $userLat is not defined and what it should read is $lat – the users postcode latitude. Thanks for pointing that out, I have now corrected it. Also, I’m glad you found my example useful.

    Regards,
    Kevin

  3. Kevin, I forgot to tell you, there’s another mistake where it says:

    The users postcode has a longitude of 54.1234 and latitude of -3.1234. A 10 mile range would be somewhere in between -3.0123 ($lonMIN) and -3.2345 ($lonMAX) latitude…

    It’s the other way around, 54.1 is the lat and -3.1 the long :)

  4. Yes indeed you are right again. It must have been another late night when I typed that out! Anyway, I’ve updated my original article. :-)

  5. Thanks for this post! I had my proximity class, but I had as granted that the earth was plain :-$

    By the way: for non US programmers, just remember that 1 mile is 1.609344 kilometers, so if you want to use this script for distances in Km just substitute $radius = 20 with:

    $radius = $radius_in_km * 0.621371192;

    And finally: what about implementing the “Altitude” variable here? Funnier ;-)

  8. very usefull article, thanks a lot :)
    in php implementation I first had a very dirty bug. All longitude and latitude results came with ‘,’ in place of a ‘.’ so result were just crazy so I add str_replace(‘,’,’.’,$var) and now it works perfect.
    I know it look dirty but it works :) if someone got an answer…

  11. Great article, thanks for sharing. I can understand how i could return geolocations within a certain radius now.

    I have one question though, if i was going to return locations within say 10 miles of a post code, if i had multiple rows returned how could I work out the proximity of each of them in miles and order the data thus.

    eg. Acme Ltd 5.2miles away, Smith & Sons Ltd 5.8miles away etc.

  12. Here’s what I’m using. Feel free to adapt it to the DB or framework you are using:

    set @latitude=52.25338;
    set @longitude=1.10245;
    set @radius=10; # in kms

    set @lng_min = @longitude – @radius/abs(cos(radians(@latitude))*69);
    set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
    set @lat_min = @latitude – (@radius/69);
    set @lat_max = @latitude + (@radius/69);

    SELECT *,
    3956 * 2 * ASIN(SQRT(POWER(SIN((@latitude – abs(p.latitude)) * pi()/180 / 2), 2) + COS(@latitude * pi()/180) * COS(abs(p.latitude) * pi()/180) * POWER(SIN((@longitude – p.longitude) * pi()/180 / 2), 2))) AS distance
    FROM postcode AS p
    LEFT JOIN county AS c ON (c.id = p.county_id)
    WHERE (p.longitude BETWEEN @lng_min AND @lng_max)
    AND (p.latitude BETWEEN @lat_min and @lat_max)
    HAVING distance < @radius
    ORDER BY distance ASC;

  13. Hi There,

    I am planning on using this with Google Maps on a website that will have more than 5000 records to go through.

    My only question is what is the performance like of this script if I am to run it on 5000 or more records…

    Please help.

    Regards,
    Zahid

  15. Now then Fede!

    Always nice to see a blog I’m familiar with showing up in google searches.

    Which implementation do you prefer, handing over to the SQL or giving the sql the lat/long constraints?

  19. Thanks for posting this!
    There are just a couple things I don’t get, though, and forgive me if my questions will be stupid:
    1) what does that “69” stand for?
    2) is it necessary to convert km in miles?

    Thank you so much

  20. 1. nothing its just a parameter for calculating distance
    2. no it is not necessary to covert km in miles. use
    $radius = $radius_in_km * 0.621371192;

  21. This looks very interesting and possibly what I am after. Can I utilise this to initiate some form of proximity detection? I have a google map that users can add a marker to (They don’t see any other markers). I need to stop a new marker being placed within 3 miles of a lat/long that already exists in my ms-sql 2008 database. I am coding in php.

    Any help gratefully appreciated, as this has been wearing me down and i’m coming close to needing a toupee to cover the clusters of hair I have ripped out!

  23. Using the python version of this code for a small personal project (looking at drive times from Real estate while house hunting). Thank you very much for posting this.

  24. EXCELLENT! This is why god invented the blog, so people can get this type of excellent information. Thank you so much for the knowledge.

  25. Hi Federico;
    This is Java impl. (double for simplicity)

    double longitude = -2.708077;
    double latitude = 53.754842;
    double radius = 20;

    double lonMin = longitude – radius / Math.abs(Math.cos(Math.toRadians(latitude)) * 69);
    double lonMax = longitude + radius / Math.abs(Math.cos(Math.toRadians(latitude)) * 69);
    double latMin = latitude – (radius / 69);
    double latMax = latitude + (radius / 69);

    System.out.println(String.format(“lng (min/max): %.13f %.13f”, lonMin, lonMax));
    System.out.println(String.format(“lat (min/max): %.12f %.12f”, latMin, latMax));

  27. This helped me out, so just in case someone else comes looking for a JAVA implementation.

    Java Implementation if anyone comes looking.

    float longitude = locationObj.getLongitude();
    float latitude = locationObj.getLatitude();
    float radiusInKm = (float) (geoProximtyObj.getRadius() * 0.621371192); // Kilometers

    float lng_min = (float) (longitude – radiusInKm / Math.abs(Math.cos(Math.toRadians(latitude)) * 69));
    float lng_max = (float) (longitude + radiusInKm / Math.abs(Math.cos(Math.toRadians(latitude)) * 69));
    float lat_min = latitude – (radiusInKm / 69);
    float lat_max = latitude + (radiusInKm / 69);

    SQL:

    “SELECT * FROM POI WHERE (j.longitude BETWEEN ?1 AND ?2) AND (j.latitude BETWEEN ?3 and ?4)”

Leave a comment