MySQL query for WGS-84 longitude & latitude radius GPS distance calculation

WGS-84 Proximity Search with Longitude & Latitude decimal co-ordinates

Example: Hotel Burnham in Downtown Chicago is located at:
1 West Washington Street, Chicago, IL
Latitude: 41.883190
Longitude: -87.627940

I absolutely want to help some people out there with the same problem I
faced. I spent all night scanning lines of code trying SQL and C# code
that simply just DOES NOT work. There is TONS of crap code scattered
all over the internet, but very many great articles explaining how
everything works, so I piggybacked on the knowledge out there to get a
working solution. For those like me, you just want to use the code and
hit the ground running.

The basis of my calculation is derived from a Microsoft White Paper.

So here goes, d = distance, is the final output of this equation. R =
the earth's radius (and can be in m, km, mi or nm) The values 'a', 'b'
and 'c' are just steps to break the formula into digestable chunks:

a = sin(lat1)*sin(lat2)
b = cos(lat1)*cos(lat2)*cos(lon2-lon1)
c = acos(a+b)
d = R*c

The earth's radius is:
6378137 meters
6378.137 km
3963.191 miles
3441.596 nautical miles

Simply choose the value for R, for your desired distance results.
Example: R = 3963.191 (OR d = 3963.191*c) will return distance from
main point of interest in miles, use 6378.137 instead as the R
parameter and get a result in KM's

Other constants, MySQL actually has a function called "PI()" which I
will use in this example, but its precision is not quite as great as
the number below:
PI = 3.141592653589793

SELECT 3963.191 * ACOS( (SIN(PI()*41.883190/180)*SIN(PI()*MapLat/180))
+
(COS(PI()*41.883190/180)*cos(PI()*MapLat/180)*COS(PI()*MapLong/180-PI()*-87.627940/180))
), Company, Address FROM boomtrek.poi WHERE City = 'Chicago'

The fields in my database are MapLat and MapLong for the decimal
degrees values that work with Google Maps WGS-84 standard. I found that
the majority of tutorials out there neglected to give much info on the
parameters being passed into the method, just simply the method.

NOTE: all latitude/longitude inputs must be converted into RADIANS!!

The calculate for decimal degrees like 'lat1' (41.883190) to radians
is:
PI() * lat1 / 180
OR
3.14159 * 41.883190 / 180

lon1 input is like this:
PI() * -87.627940 / 180
....to convert decimal degrees into radians.

lat1 & lon1 input parms - should be the fixed point where you want to
search proximity, this is the point of interest to find things nearby
it, in this case:
(1 West Washington Street, Chicago, IL)
Latitude: 41.883190
Longitude: -87.627940

MapLat = lat2 input parameter (MapLat = the MySQL field in the database
for the latitude geocoding)
MapLong = lon2 input parameter (MapLong is the MySQL longitude field in
the database)

For Mapping; tacking the same stuff as the SELECT clause on to the
WHERE clause one can find points within a 1.5 mile radius, and reduce
the resultset size, displaying all points on one map page, between
10-25 points should be a great number.

AND 3963.191 * ACOS( (SIN(PI()*41.883190/180)*SIN(PI()*MapLat/180)) +
(COS(PI()*41.883190/180)*cos(PI()*MapLat/180)*COS(PI()*MapLong/180-PI()*-87.627940/180))
) <= 1.5 LIMIT 25

And finally; using an ORDER BY with the same stuff yet again you could
find the things closet to your proximity where you're standing or
driving:

ORDER BY 3963.191 * ACOS(
(SIN(PI()*41.883190/180)*SIN(PI()*MapLat/180)) +
(COS(PI()*41.883190/180)*cos(PI()*MapLat/180)*COS(PI()*MapLong/180-PI()*-87.627940/180))
)

I really hope this was of use to some people, you can see the mapping
and proximity searching in action at Boomtrek Local Search:
http://www.boomtrek.com/search.aspx?region=us-chicago&keywords=hotel+downtown

Happy coding!
Boomtrek Travel Services
www.boomtrek.com
boomtrek@hotmail.com (MSN)

boomtrek@hotmail.com wrote:
(COS(PI()*41.883190/180)*cos(PI()*MapLat/180)*COS(PI()*MapLong/180-PI()*-87.627940/180))

But if your database has millions of records in it, this will be a very
slow query since it will have to calculate the above value on every single
row in the database and thus cannot take advantage of indices.


Cheers,
-+JLS

--
\ carpe cavy!
seagull @ aracnet.com \
http://www.aracnet.com/~seagull/ \ (seize the guinea pig!)

Indeed and the suggestion of the same calculation in the sort will make
it even slower as it is evaluated twice for every record.

A better (faster & less load on the server) approach is:

Use the query to select only those records that could possibly
be within the specified distance to the point in question by
simple arithmetic (e.g. within a certain Lat / Long window).

Loop through the results obtained in the first step calculating
the distance and display only those points within the desired
distance.

Programmatically I would take the point and the desired distance as
parameters for a script. Calculate the change in Lat and Long equivalent
to that distance at that point. Build the MySQL query with those values.
Run the query. Loop through the array of results from the query
calculating the distance from the point of interest and displaying those
points within the specified distance.

If the output must be sorted closest first the processing loop can add
the points that are within the specified distance to an array which is
then sorted and displayed.

--

Dominic Sexton

The way I did it (searching for waypoints within a certain distance in
miles) was to just compute the miles/degree (or km/degree or whatever)
for the input latitude. Compute an offset by multiplying the miles you
want to search by degrees/mile to get a value in degrees. The math to
do this isn't too ugly.

Assuming you are storing your coords as a floating point number (the
only way that really makes sense), you you simply query for waypoints
current_lon+offset.

The downside of this is you are really searching a bounding rectangle
instead of a circle, but it's close enough for MOST uses (mine at
least).

Good luck!

Here's some code I did in PHP for a website project. Perhaps it will
help you, though it's a bit or a hack, and PHP is a bit limiting with
it's math functions, but this did work for me. Warning: I cut and
pasted, added some comments, clarified a few things - don't expect this
to work out of the box, but hopefully it helps.

$la= FILLME #put input latitude here
$lo= FILLME #put input longitude here
$miles=FILLME #put distance to search here in miles

$ra=deg2rad($la);
$rs=acos(cos($ra)*cos($ra)*cos(deg2rad(1))+sin($ra)*sin($ra));
$mpd=$rs*3959.0; # Now we have miles per degree

$dpm=1/$mpd; # Now we have degrees per mile
$dts=$dpm*$miles; # And finally here's our answer - we need to
search this many degrees


$las=$la-$dts; # Southern boundary
$lan=$la+$dts; # Northern boundary
$low=$lo-$dts; # Western boundary
$loe=$lo+$dts; # Eastern boundary


$query="SELECT ID, Latitude,Longitude FROM waypoints where Latitude <=

# I also need to calculate the exact distance from the input point and
found points
# I used the following for each resulting waypoint from the query:

$a1=deg2rad($la);
$b1=deg2rad($lo);
$a2=deg2rad($tlat);
$b2=deg2rad($tlon);
$dist=acos(cos($a1)*cos($b1)*cos($a2)*cos($b2) +
cos($a1)*sin($b1)*cos($a2)*sin($b2) + sin($a1)*sin($a2)) * 3963.1;

Again, this was something I tossed together for a particular need I
had, it may or may not work for you, but hopefully it helps!

scotte wrote:


This is a very good approach, using subqueries you could then do a
circular select within the first result set, which would be very fast
indeed.


You should possibly consider what happens if you cross the 180 degree
line? One approach is to simply translate all coordinates by subtracting
the target, i.e. delta coordinates only.

This allows you to calculate the bounding square with two instead of
four compares:

where abs(delta_lat) <= bound_lat and abs(delta_lon) <= bound_lon

For the range of distances where this will be used, a flat approximation
to local offsets might be more than good enough, in which case the
actual offset can be calculated using Phytagoras:

where (delta_lat*delta_lat + delta_lon*delta_lon*lon_scale_squared) <=
limit_squared

Terje

--
"almost all programming can be viewed as an exercise in caching"