MySQL Forums
Forum List  »  GIS

Re: Zip Code Proximity search
Posted by: p dontthink
Date: June 25, 2006 09:32PM

@tri: You should tell people WHAT UNITS your query is in.

I just waded through this thread and a bunch of google search results and implemented a lookup where I am searching for things within a given radius. I coded it to do the full distance/radius calculation and comparison in MySQL *OR* to use the nifty idea from this thread of looking up a "sloppy rectangle" of results in MySQL and refining the results set in PHP... so I did a bit of testing:

My initial thought was that MySQL would be faster, but tests against a very small data set showed PHP to be a touch under twice as fast. Perhaps that will change drastically once I have a large dataset and a server under full load.

People's explanations here weren't too clear about constructing that rectangle, so here's something more concrete in PHP. Units used are miles, but you can change that easily enough by converting the 69.172 number to KM or whatever unit you want.

$sql = 'SELECT ... FROM items ... WHERE';

$distance_lookup_slop_miles = 5;

$delta_latitude = (($radius + $distance_lookup_slop_miles) / 69.172);
$lat1 = $latitude + $delta_latitude;
$lat2 = $latitude - $delta_latitude;
$delta_longitude = (($radius + $distance_lookup_slop_miles)
/ (cos($latitude) * 69.172));
$long1 = $longitude + $delta_longitude;
$long2 = $longitude - $delta_longitude;
$sql .= ' AND items.latitude <= ' . $lat1
. ' AND items.latitude >= ' . $lat2
. ' AND items.longitude <= ' . $long1
. ' AND items.longitude >= ' . $long2;

I also had to implemenet a SORT based on distance, which is independent of whether or not the lookup is based on distance. That means that unless I wanted to pull ALL rows out and then re-order them by distance (where distance is possibly NOT the first row in the ORDER BY clause - what a PHP nightmare THAT would be), then I have to include some of the distance math in the SQL. What I did for that was to simply trim down the math so that the "distance" it calculates is NOT the final real distance, but is just enough such that the sort will work. That looks something like this, again in PHP:

$sql = 'SELECT ... '
. ' ((items.latitude - ' . $latitude . ') * (items.latitude - '
. $latitude . ') + cos(items.latitude / 57.29578) * cos('
. $latitude . ' / 57.29578) * (items.longitude - '
. $longitude . ') * (items.longitude - ' . $longitude
. ')) as distance '
. ' FROM items ...'
. ' ORDER BY ..., distance, ...';

Just be careful not to use that "distance" number for anything but sorting. The full actual distance would look more like the following (this is what I used to compare the SQL and PHP-based lookups). As I said, it is slower than PHP under light load, but the resulting values are actually pretty accurate (again, in miles):

$sql = 'SELECT ... '
. ' (3958 * 3.1415926 * sqrt((items.latitude - ' . $latitude
. ') * (items.latitude - ' . $latitude
. ') + cos(items.latitude / 57.29578) * cos('
. $latitude . ' / 57.29578) * (items.longitude - '
. $longitude . ') * (items.longitude - ' . $longitude
. ')) / 180) as distance '
. ' FROM items ...'
. ' WHERE ...'
. ' HAVING distance <= ' . $radius;

Note here that you CANNOT use "distance" in the WHERE clause because column aliases are not allowed in the WHERE clause (see the manual). Thus, the HAVING clause.

Oh, and you should be asking me what calculation method I used in PHP, because that is important to know when you are making comparisons. I wrote a library that allows me to switch between Great Circle, Haversine, and Vincenty. I also added the ability to include a more accurate radial calculation that I found here:

http://wantingseed.com/sprout/2003/06/10/distance-between-two-points-on-earth/

Using that more accurate mean radius in the Great Circle or Haversine formulas got me results that were really darn close to the Vincenty results, but still noticably faster (OK, even thousands of nanoseconds is not noticable to a human...). So I settled on a fast but reasonably accurate (by using the better radial value) Great Circle calculation.

HTH

Options: ReplyQuote


Subject
Views
Written By
Posted
28053
October 19, 2004 06:04AM
10836
October 19, 2004 07:55AM
9237
October 19, 2004 11:14AM
10277
October 21, 2004 09:28AM
9163
October 19, 2004 06:59PM
7614
October 20, 2004 07:39AM
7628
October 21, 2004 09:10AM
8820
October 22, 2004 07:17AM
6759
October 23, 2004 02:48AM
6220
October 23, 2004 03:09AM
6312
October 23, 2004 03:12AM
6205
October 23, 2004 02:59PM
7982
October 24, 2004 12:34PM
5513
October 24, 2004 01:31PM
13108
October 21, 2005 10:21AM
5565
D C
January 28, 2006 05:24AM
5109
March 02, 2006 04:24PM
7208
October 09, 2007 09:28AM
5734
December 06, 2005 05:34AM
7002
December 06, 2005 06:36AM
5306
December 24, 2005 01:10PM
8823
December 26, 2005 03:49PM
5432
October 09, 2007 09:36AM
29331
December 13, 2007 04:10PM
6175
April 05, 2006 02:59PM
4697
May 02, 2006 03:22PM
5659
May 05, 2006 09:44AM
Re: Zip Code Proximity search
14502
June 25, 2006 09:32PM
5487
August 30, 2006 12:54PM
5974
July 14, 2007 01:09AM
7629
November 03, 2006 10:25AM


Sorry, you can't reply to this topic. It has been closed.

Content reproduced on this site is the property of the respective copyright holders. It is not reviewed in advance by Oracle and does not necessarily represent the opinion of Oracle or any other party.