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

That’s it. Happy Geolocating!

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

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

Yours was one of the best examples, thanks for posting it :)

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 :)

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. :-)

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 ;-)

Ah! I had written something very similar in May 2003 (Yikes! that is long ago) for php arch magazine – http://www.scribd.com/doc/303111/article-9

Interesting, thanks Tarique.

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…

[…] PHP::Impact tiene un artículo muy interesante sobre como hacer busquedas por proximidad geográfica: Geo Proximity Search with PHP, Python and SQL. […]

[…] – Geo Proximity Search with PHP, Python and SQL […]

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.

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;

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

Thank you, this is very very useful!

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?

Hi Dave :)

Check out the following PDF, specially the part where it says “How to speed up the query”:

Click to access geo_search.pdf

MySQL is slow, I recommend using http://sphinxsearch.com to perform geo distance search.

Cheers buddy, I’m familiar with Lucene/Solr but haven’t seen Sphinx before, I’ll check it out.

Mitico!!!

Mi hai risparmiato un bel po’ di lavoro :-)

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

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;

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!

Yes, you can:

https://blog.fedecarg.com/2009/02/08/geo-proximity-search-the-haversine-equation/#comment-4528

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.

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

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));

Thank you so much. It helped me a lot.

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)”