Find long/lat's within 20 miles of user's long/lat

Question

I'm working on an application where a user can search for items near his location.

When a user registers for my service, their long/lat coordinates are taken (this is actually grabbed from a zip/postcode and then gets looked up via Google for the long/lats). This also happens when a user adds an item, they are asked for the zip/postcode of the item, and that is converted to the long/lat.

My question is how would i run a query using MySQL that would search within, say 20 miles, from the user's location and get all the items within that 20 mile radius?

score 2 · Accepted Answer · answered Sep 14 '11 at 09:04

2

Assuming precision isn't really an issue (taking a square instead of a circle, and ignoring terrain), you could do something like this:

SELECT ... FROM ...
WHERE (ABS(firstLong - secondLong) < 20) AND (ABS(firstLat - secondLat) < 20);

If you do wish to make it a circle instead, just write a slightly more complicated mathematical formula for the distance: SQRT(longDelta*longDelta + latDelta*latDelta) < 20

answered Sep 14 '11 at 09:04

Eran Zimmerman Gonen

4,375
1
19
31

5

Your formulas both assume that len(1 degree of latitude) == len(1 degree of longtitude) (true only at the equator) and that both == one mile (quite wrong). The length of one degree of longitude varies with latitude, becoming zero at the poles. At a latitude like that of Seattle, the error is serious. – John Machin Sep 14 '11 at 11:35
3

This answer is wrong. As John Machin mentioned, lat/lon are in units of degrees while 20 is in units of miles. – TreyA Sep 14 '11 at 18:47

score 2 · Answer 2 · answered Sep 14 '11 at 09:05

When you store the lat/lon data, you can also store what's called a "geospatial index", which is basically a string that encodes both pieces of data at once. One such indexing scheme is the Geohash algorithm, which uses a sequence of bits to subdivide the globe into increasingly small boxes.

Then, when you want to search by distance, you first narrow the scope of the search based on the geohash, then filter results by testing the Euclidean distance or using the Haversine formula.

Another option is to use a separate database specifically for performing this kind of query. For example MongoDB natively supports geospatial indexing, and CouchDB can do it with a little help from geocouch.

Skipping back to MySQL, this presentation may be of some help: Geo Distance Search with MySQL

-1 `Euclidean_distance = earth_radius * sqrt(delta_lat ** 2 + delta_lon ** 2)` is OK in Ecuador but dismally inaccurate in Alaska. — John Machin, Sep 15 '11 at 20:56

score 1 · Answer 3 · answered Dec 15 '16 at 02:31

1

In python you can use a kdtree, try out this code snippet:

first, you would need to install pysal

import pysal
from pysal.cg.kdtree import KDTree    

locations = [(40.702566, -73.816859),
         (40.70546, -73.810708),
         (40.709179, -73.820574),
         (40.700486, -73.807969),
         (40.694624, -73.820593),
         (40.695132, -73.820841),
         (40.694095, -73.821334),
         (40.694165, -73.822368),
         (40.695077, -73.822817),
         (40.6747769261, -73.8092618174)] 
tree = KDTree(locations, distance_metric='Arc', radius=pysal.cg.RADIUS_EARTH_MILES)
current_point = (40.709523, -73.802472)
# get all points within 1 mile of 'current_point'
indices = tree.query_ball_point(current_point, 1)
for i in indices:
    print(locations[i])

answered Dec 15 '16 at 02:31

salah

439
4
7

Thanks for this, exactly what I needed and super simple to use! :) – Sverrir Sigmundarson Apr 09 '18 at 09:09
This doesn't seem to be accurate over about 5-10 miles. – Mike C. Mar 28 '19 at 18:04
https://crosscompute.com/n/4NpIfkK5A8OzOTws1awyqfR1cgOcVlQV/-/kdtree looks good to me, can you provide the data? – salah Mar 29 '19 at 02:09
you should change the spatial reference system to utm before passing in the kd tree https://ocefpaf.github.io/python4oceanographers/blog/2013/12/16/utm/ – salah Aug 23 '19 at 13:01

score 1 · Answer 4 · answered Sep 14 '11 at 09:08

Depending on the platform you are using there are several options:

Brute force - take the items in the database and run a linear geo distance function between your long/lat and the coordinates of the items something like this:

public decimal GeoDistance(decimal lat1, decimal lng1, decimal lat2, decimal lng2)
{
    double r = 6378.7; //km

    decimal p = (decimal)(Math.PI / 180.0);
    lat1 *= p; lat2 *= p; lng1 *= p; lng2 *= p;

    return (decimal)(r * (Math.Acos(Math.Sin((double)lat1) * Math.Sin((double)lat2) + Math.Cos((double)lat1) * Math.Cos((double)lat2) * Math.Cos((double)lng2 - (double)lng1))));
}

If you are using MS SQL Server 2008 (other database engines might also support) you can use geography methods

score 0 · Answer 5 · edited May 23 '17 at 11:53

0

You might find a previous answer of mine of interest which is very performant:

Calculate distance between zip codes and users

"Find nearest location" by Zip/Postal Code?

Hope this helps :)

edited May 23 '17 at 11:53

Community

1
1

answered Sep 14 '11 at 11:24

Jon Black

16,223
5
43
42

1

This should have been a comment, not an answer. – Mark Ransom Sep 14 '11 at 17:10
1

@Mark, it's my attempt at a bump :P – Jon Black Oct 21 '11 at 11:44

score 0 · Answer 6 · answered Sep 14 '11 at 17:51

To be performant, you don't want to do a complete scan through the database and compute distances for each row, you want conditions that can be indexed. The simplest way to do this is to compute a box with a minimum/maximum latitude and minimum/maximum longitude, and use BETWEEN to exclude everything outside of those ranges. Since you're only dealing with US locations (zip code based), you won't have to worry about the transition between +180 and -180 degrees.

The only remaining problem is to compute the bounds of the box in lat/long when your conditions are in miles. You need to convert miles to degrees. For latitude this is easy, just divide 360 degrees by the circumference of the earth and multiply by 20; 0.289625 degrees. Longitude is tougher because it varies by latitude, the circumference is roughly cosine(latitude)*24901.461; 20 miles is 20*360/(cos(latitude)*24901.461).

Find long/lat's within 20 miles of user's long/lat

6 Answers6