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
That’s it. Happy Geolocating!
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
Kevin
February 8, 2009 at 3:53 pm
Yours was one of the best examples, thanks for posting it :)
Federico
February 8, 2009 at 4:11 pm
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 :)
Federico
February 8, 2009 at 7:15 pm
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. :-)
Kevin
February 8, 2009 at 8:53 pm
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 ;-)
Nacho
February 9, 2009 at 12:10 pm
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
Tarique Sani
February 10, 2009 at 6:05 am
Interesting, thanks Tarique.
Federico
February 10, 2009 at 8:52 pm
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…
mikeRKL
February 10, 2009 at 10:49 pm
[...] PHP::Impact tiene un artículo muy interesante sobre como hacer busquedas por proximidad geográfica: Geo Proximity Search with PHP, Python and SQL. [...]
Búsqueda por proximidad geográfica en PHP — kodrs
February 11, 2009 at 5:15 pm
[...] - Geo Proximity Search with PHP, Python and SQL [...]
Les liens de la semaine | Oxeron Internet and Mobile Service Sarl
February 13, 2009 at 11:12 am
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.
Ben Palmer
September 16, 2009 at 11:49 pm
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;
Federico
September 17, 2009 at 9:36 am
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
Zahid
January 21, 2010 at 8:19 pm
Thank you, this is very very useful!
arik
July 9, 2010 at 3:05 pm
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?
Dave Marshall
October 6, 2010 at 7:21 pm
Hi Dave :)
Check out the following PDF, specially the part where it says “How to speed up the query”:
http://www.arubin.org/files/geo_search.pdf
MySQL is slow, I recommend using http://sphinxsearch.com to perform geo distance search.
Federico
October 7, 2010 at 3:48 pm
Cheers buddy, I’m familiar with Lucene/Solr but haven’t seen Sphinx before, I’ll check it out.
Dave Marshall
October 8, 2010 at 11:18 am
Mitico!!!
Mi hai risparmiato un bel po’ di lavoro :-)
Andrea
October 27, 2010 at 9:40 pm
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
V83
May 2, 2011 at 3:44 pm
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;
dhiru
June 22, 2011 at 8:36 am
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!
David C
August 16, 2011 at 3:27 pm
Yes, you can:
http://blog.fedecarg.com/2009/02/08/geo-proximity-search-the-haversine-equation/#comment-4528
Federico
August 18, 2011 at 2:24 pm
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.
Tandeson
August 28, 2011 at 3:42 am
EXCELLENT! This is why god invented the blog, so people can get this type of excellent information. Thank you so much for the knowledge.
tanner
October 19, 2011 at 11:30 am