CODEWITHSUNDEEP
pythonmysqlgeolocationlatitude-longitude
dotty
dotty

Reputation: 41483

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

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?

Upvotes: 3

Views: 4880

Answers (6)

salah
salah

Reputation: 504

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

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308482

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

Upvotes: 0

Jon Black
Jon Black

Reputation: 16559

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

Upvotes: 0

Pasman
Pasman

Reputation: 445

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

Upvotes: 1

jimbo
jimbo

Reputation: 11042

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

Upvotes: 2

Eran Zimmerman Gonen
Eran Zimmerman Gonen

Reputation: 4507

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

Upvotes: 2

Related Questions