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
28584
October 19, 2004 06:04AM
10953
October 19, 2004 07:55AM
9360
October 19, 2004 11:14AM
10391
October 21, 2004 09:28AM
9273
October 19, 2004 06:59PM
7729
October 20, 2004 07:39AM
7737
October 21, 2004 09:10AM
8996
October 22, 2004 07:17AM
6925
October 23, 2004 02:48AM
6340
October 23, 2004 03:09AM
6475
October 23, 2004 03:12AM
6339
October 23, 2004 02:59PM
8117
October 24, 2004 12:34PM
5618
October 24, 2004 01:31PM
13283
October 21, 2005 10:21AM
5677
D C
January 28, 2006 05:24AM
5236
March 02, 2006 04:24PM
7329
October 09, 2007 09:28AM
5845
December 06, 2005 05:34AM
7153
December 06, 2005 06:36AM
5415
December 24, 2005 01:10PM
8983
December 26, 2005 03:49PM
5558
October 09, 2007 09:36AM
29576
December 13, 2007 04:10PM
6281
April 05, 2006 02:59PM
4827
May 02, 2006 03:22PM
5813
May 05, 2006 09:44AM
Re: Zip Code Proximity search
14757
June 25, 2006 09:32PM
5620
August 30, 2006 12:54PM
6133
July 14, 2007 01:09AM
7741
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.