Sorting MySQL query by Latitude/Longitude

Question

Every user in my database has their latitude and longitude stored in two fields (lat, lon)

The format of each field is:

lon | -1.403976 
lat | 53.428691

If a user searches for other users within, say 100 miles, I perform the following in order to calculate the appropriate lat/lon range ($lat and $lon are the current users values)

$R = 3960;  // earth's mean radius
$rad = '100';
// first-cut bounding box (in degrees)
$maxLat = $lat + rad2deg($rad/$R);
$minLat = $lat - rad2deg($rad/$R);
// compensate for degrees longitude getting smaller with increasing latitude
$maxLon = $lon + rad2deg($rad/$R/cos(deg2rad($lat)));
$minLon = $lon - rad2deg($rad/$R/cos(deg2rad($lat)));

$maxLat=number_format((float)$maxLat, 6, '.', '');
$minLat=number_format((float)$minLat, 6, '.', '');
$maxLon=number_format((float)$maxLon, 6, '.', '');
$minLon=number_format((float)$minLon, 6, '.', '');

I can then perform a query such as:

$query = "SELECT * FROM table WHERE lon BETWEEN '$minLon' AND '$maxLon' AND lat BETWEEN '$minLat' AND '$maxLat'";

This works fine, and I use a function to calulate and display the actual distance between users at output stage, but I'd like to be able to sort the results by decreasing or increasing distance at the query stage.

Is there any way of doing this?

Blazemonger · Accepted Answer · 2013-05-09T16:39:32.413

44

Remember Pythagoras?

$sql = "SELECT * FROM table 
    WHERE lon BETWEEN '$minLon' AND '$maxLon' 
      AND lat BETWEEN '$minLat' AND '$maxLat'
    ORDER BY (POW((lon-$lon),2) + POW((lat-$lat),2))";

Technically that's the square of the distance instead of the actual distance, but since you're just using it for sorting that doesn't matter.

This uses the planar distance formula, which should be good over small distances.

HOWEVER:

If you want to be more precise or use longer distances, use this formula for great circle distances in radians:

dist = acos[ sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lng1-lng2) ]

(To get the distance in real units instead of radians, multiply it by the radius of the Earth. That's not necessary for ordering purposes, though.)

Latitude and longitude is assumed by the MySQL computation engine to be in radians, so if it's stored in degrees (and it probably is), you'll have to multiply each value by pi/180, approximately 0.01745:

$sf = 3.14159 / 180; // scaling factor
$sql = "SELECT * FROM table 
    WHERE lon BETWEEN '$minLon' AND '$maxLon' 
      AND lat BETWEEN '$minLat' AND '$maxLat'
    ORDER BY ACOS(SIN(lat*$sf)*SIN($lat*$sf) + COS(lat*$sf)*COS($lat*$sf)*COS((lon-$lon)*$sf))";

or even:

$sf = 3.14159 / 180; // scaling factor
$er = 6350; // earth radius in miles, approximate
$mr = 100; // max radius
$sql = "SELECT * FROM table 
    WHERE $mr >= $er * ACOS(SIN(lat*$sf)*SIN($lat*$sf) + COS(lat*$sf)*COS($lat*$sf)*COS((lon-$lon)*$sf))
    ORDER BY ACOS(SIN(lat*$sf)*SIN($lat*$sf) + COS(lat*$sf)*COS($lat*$sf)*COS((lon-$lon)*$sf))";

edited May 09 '13 at 16:39

answered May 09 '13 at 15:50

Blazemonger

90,923
26
142
180

Thanks Blaze, that seems to be working - there's one or two out of place but it's not a dealbreaker (unless you can think of how I can get around it). Upvote regardless. Thanks – Dan May 09 '13 at 16:01
Are they actually out of place according to the squared-distance? Or do you think the squared-distance was computed incorrectly? – Blazemonger May 09 '13 at 16:03
1

That query doesn't account for the fact that longitude is measured east-west from the Greenwich meridian, so it will return very long distances for two places near each other and near the 180th meridian. – nitro2k01 May 09 '13 at 16:03
Just something to be aware of. Other people might google and find this answer and want to use it for longer distances. – nitro2k01 May 09 '13 at 16:06
Blaze - I honestly have no idea - it seems entirely accurate when distances are calculated for display (e.g. 23 miles away). – Dan May 09 '13 at 16:06
@Dan - I would strongly suggest you see my answer below. Using @Blazemonger 's `BETWEEN` is not always accurate enough, querying a square area as opposed to a radius from your location. – lukeocodes May 09 '13 at 16:15
1

Added a more precise formula, borrowed from Wikipedia. – Blazemonger May 09 '13 at 16:27
You are also a gentleman - thank you so much - seems to work a treat straight out of the box – Dan May 09 '13 at 16:38
2

It's been fun and educational. :-) – Blazemonger May 09 '13 at 16:41
Awesome, old and still very useful. Minor note; the comments say $er=6350; 'earth radius in *miles*'. But mean earth radius is 6371.0 *km* or 3958.8 miles. – rob Feb 15 '19 at 19:25

lukeocodes · Answer 2 · 2014-03-18T15:09:40.203

8

Using just SELECT * FROM Table WHERE lat between $minlat and $maxlat will not be accurate enough.

The correct way to query distance is using the coordinates in radians.

<?php
  $sql = "SELECT * FROM Table WHERE acos(sin(1.3963) * sin(Lat) + cos(1.3963) * cos(Lat) * cos(Lon - (-0.6981))) * 6371 <= 1000";

Here is a handy reference - http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates

For example:

<?php
  $distance = 100;
  $current_lat = 1.3963;
  $current_lon = -0.6981;
  $earths_radius = 6371;

  $sql = "SELECT * FROM Table T WHERE acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius <= $distance";

And if you want to do the order by and show the distance:

<?php
  $distance = 100;
  $current_lat = 1.3963;
  $current_lon = -0.6981;
  $earths_radius = 6371;

  $sql = "SELECT *, (acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius) as distance FROM Table T WHERE acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius <= $distance ORDER BY acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius DESC";

Edited for @Blazemonger and the avoidance of doubt :) If you want to work in degrees instead of radians:

<?php
  $current_lat_deg = 80.00209691585;
  $current_lon_deg = -39.99818366895;
  $radians_to_degs = 57.2957795;

  $distance = 100;
  $current_lat = $current_lat_deg / $radians_to_degs;
  $current_lon = $current_lon_deg / $radians_to_degs;
  $earths_radius = 6371;

  $sql = "SELECT *, (acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius) as distance FROM Table T WHERE acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius <= $distance ORDER BY acos(sin($current_lat) * sin(T.Lat) + cos($current_lat) * cos(T.Lat) * cos(T.Lon - ($current_lon))) * $earths_radius DESC";

You could easily wrap this up into a class that accepted Radians or Degrees from the information provided above.

edited Mar 18 '14 at 15:09

answered May 09 '13 at 16:14

lukeocodes

1,192
1
16
31

I've my fair share of geo-location apps using this exact code. No complaints so far! :) – lukeocodes May 09 '13 at 16:18
Luke, I appreciate the answer but it's a bit confusing to me - could you edit it using my $max and $min variables in the correct places? I hate to ask but, well, you know :) – Dan May 09 '13 at 16:20
No problem, give it a test! – lukeocodes May 09 '13 at 16:29
Aren't you assuming lat and lng are stored in radians in the database? 'Cause they're not, as far as I can tell. – Blazemonger May 09 '13 at 16:33
@Blazemonger - Based on his question, they are... columns named lat and lon. – lukeocodes May 10 '13 at 10:59
1

He gives the example `lat | 53.428691` -- that number is too large to be in radians. – Blazemonger May 10 '13 at 13:08
@LukeOliff ? I was talking about radians, not degrees. – Blazemonger Mar 17 '14 at 14:32
@Blazemonger It can be easily modified to handle Radian's instead. 1 Radian = 57.2957795 Degrees – lukeocodes Mar 18 '14 at 14:58
@TheSexiestManinJamaica This has nothing to do with Google Maps? And changing the order by whether you want the closest first or the furthest first is simple a case of changing the order by. This query is verified by the very fact it's used on a hotel search site whereby people can search for the hotels within X kilometers to Y destination/tourist spot. – lukeocodes Jul 14 '15 at 07:44
Hey, what unit is the distance? Is it in kilometers? Thank! – Sascha Grindau Sep 08 '19 at 12:29
1

Hey @SaschaGrindau, the earth's radius and search radius are in kilometres. Hope this helps. – lukeocodes Jan 10 '20 at 12:02

score 6 · Answer 3 · answered Jul 11 '15 at 17:58

6

This is the formula that gave me the correct results (as opposed to the solutions above). Confirmed by using the Google Maps "Measure distance" feature (direct distance, not the transportation distance).

SELECT
    *,
    ( 3959 * acos( cos( radians(:latitude) ) * cos( radians( latitude ) ) * cos( radians( longitude ) - radians(:longitude) ) + sin( radians(:latitude) ) * sin( radians( latitude ) ) ) ) AS `distance`
FROM `locations`
ORDER BY `distance` ASC

:latitude and :longitude are the placeholders for the PDO functions. You can replace them with the actual values if you'd like. latitude and longitude are the column names.

3959 is the Earth radius in miles; the distance output will be in miles as well. To change it to kilometers, replace 3959 with 6371.

answered Jul 11 '15 at 17:58

ᴍᴇʜᴏᴠ

4,804
4
44
57

It's an identical answer to my own and @Blazemonger's answer. The order of the forumlae differs, but otherwise you've used PDO (when the OP doesn't) and you've forced radians by usage of the radians function in MYSQL. Not to mention, claiming other answers are misleading and downvoting willy nilly is not in the spirit of SO. – lukeocodes Jul 14 '15 at 07:59
1

Thank you for your comment. Again, I copied the queries from the answers above (including yours) and those gave me the *misleading* values - good that I've doublechecked them. So I went through my old code archives and found the query that worked for me back then. So this is just yet another (working) answer, and yes I downvoted because the other queries did not work for me. I don't see what's wrong with this, sorry. – ᴍᴇʜᴏᴠ Jul 24 '15 at 19:38
That's odd. Using my data the queries give the same answer. I'd like to see your data to compare the results! Must be something very odd going on. – lukeocodes Jul 26 '15 at 18:47
same here, the above answer gives me strange results. this one here seems accurate to me. – Sascha Grindau Sep 08 '19 at 16:29

score 1 · Answer 4 · answered Jan 28 '19 at 15:17

None of the answers above work correctly across the Greenwich meridian. The Haversine formula:

  // 6371 is the Earth's radius in km
  6371 * 2 * ASIN(SQRT( 
     POWER(SIN((lat - abs(:latitude)) * pi()/180 / 2), 2) 
      + COS(lat * pi()/180 ) * COS(abs(:latitude) * pi()/180) 
      * POWER(SIN((lon - :longitude) *  pi()/180 / 2), 2) 
  )) as distance

which I took from here and which is referenced in this answer on a similar question, does work.

score 0 · Answer 5 · answered May 09 '13 at 15:55

0

wont give you results ordered by planar distance (not accounting for curvature of the earth) but for small radius' should work out.

SELECT * from table where lon between '$minLon' and '$maxLon' and lat between '$minLat' and '$maxLat' order by (abs(lon-$lon)/2) + (abs(lat-$lat)/2);

answered May 09 '13 at 15:55

Orangepill

24,500
3
42
63

Orange, thank you and like Blaze's answer this works with a handful out of place - Blaze's seems to have one or two less out of place though. Upvoted regardless. Thank you for your answer. – Dan May 09 '13 at 16:02
1

The `/2` is superfluous because you're just comparing magnitude, and the extra parentheses are superfluous because addition already has higher precedence than division. – nitro2k01 May 09 '13 at 16:11

Sorting MySQL query by Latitude/Longitude

5 Answers5

Linked