Zip code

[News]

I have a database of zipcodes with latitude and longitude. I also have the
method of calculating the distance between two zipcodes. What I want to
know is if there is an efficient algorithm for obtaining the zip codes
within a specified distance of the first zipcode without having to retrieve
and calculate for every record in the database.

Shelly

[Philip Ronan]

Re: Zip code

"News" wrote:
[color=blue]
> I have a database of zipcodes with latitude and longitude. I also have the
> method of calculating the distance between two zipcodes. What I want to
> know is if there is an efficient algorithm for obtaining the zip codes
> within a specified distance of the first zipcode without having to retrieve
> and calculate for every record in the database.
>
> Shelly[/color]

Not really a PHP issue, but I'd try something like this:

1. Imagine a circle of the specified range centred on the target zip code.

2. Now imagine two (square-ish) boxes centred on the same point, whose sides
correspond to lines of latitude and longitude. One box just fits inside this
circle (i.e., all four corners lie exactly on the circle), and the other
just fits around the circle (i.e., the circle is tangential to all four
sides). You can calculate the corner coordinates of these boxes by simple
trigonometry.

3. Build a DB query to extract all the zip codes that lie inside the smaller
box. These all lie inside the specified range.

4. Build another DB query to extract all the zip codes that lie inside the
larger box but not inside the smaller one. These may or may not lie inside
the specified range, and will have to be tested individually.

5. If there are still a large number of zip codes to test at step 4, divide
this region into a grid based on the latitude and longitude values, and
pre-calculate a flag for each cell to indicate whether it is completely
inside or outside the region, or if it partially intersects (in which case
you will have to test the zip codes individually).


--
phil [dot] ronan @ virgin [dot] net

http://vzone.virgin.net/phil.ronan/

[R. Rajesh Jeba Anbiah]

Re: Zip code

News wrote:[color=blue]
> I have a database of zipcodes with latitude and longitude. I also have the
> method of calculating the distance between two zipcodes. What I want to
> know is if there is an efficient algorithm for obtaining the zip codes
> within a specified distance of the first zipcode without having to retrieve
> and calculate for every record in the database.[/color]

You may do that in the query itself; but the DB will definitely scan
all the records. Look at the previous discussions
<news:CWAVb.228 32$VW4.3380@new ssvr25.news.pro digy.com> (

http://groups-beta.google.com/group/comp.lang.php/msg/a1418b46576b2cd3

)

Indexing latitude and longitude might help.

--
<?php echo 'Just another PHP saint'; ?>
Email: rrjanbiah-at-Y!com Blog: http://rajeshanbiah.blogspot.com

[News]

Re: Zip code


"Philip Ronan" <invalid@invali d.invalid> wrote in message
news:BF0E9D15.3 572E%invalid@in valid.invalid.. .[color=blue]
> "News" wrote:
>[color=green]
>> I have a database of zipcodes with latitude and longitude. I also have
>> the
>> method of calculating the distance between two zipcodes. What I want to
>> know is if there is an efficient algorithm for obtaining the zip codes
>> within a specified distance of the first zipcode without having to
>> retrieve
>> and calculate for every record in the database.
>>
>> Shelly[/color]
>
> Not really a PHP issue, but I'd try something like this:
>
> 1. Imagine a circle of the specified range centred on the target zip code.
>
> 2. Now imagine two (square-ish) boxes centred on the same point, whose
> sides
> correspond to lines of latitude and longitude. One box just fits inside
> this
> circle (i.e., all four corners lie exactly on the circle), and the other
> just fits around the circle (i.e., the circle is tangential to all four
> sides). You can calculate the corner coordinates of these boxes by simple
> trigonometry.
>
> 3. Build a DB query to extract all the zip codes that lie inside the
> smaller
> box. These all lie inside the specified range.[/color]

Thanks. While waiting for an answer I did a similar thing to the above on
my own. All I did was calculate the delta latitude and longitude
(radius*360/24902) and added and subtracted from the center point. That
gave the surrounding box. From there I will have not that many zipcodes. I
can test each one for distance and see if it lies within the specified
radius. That is the simplest method.

Shelly

[Gordon Burditt]

Re: Zip code

>I have a database of zipcodes with latitude and longitude. I also have the[color=blue]
>method of calculating the distance between two zipcodes. What I want to
>know is if there is an efficient algorithm for obtaining the zip codes
>within a specified distance of the first zipcode without having to retrieve
>and calculate for every record in the database.[/color]

It depends on what you are doing, and how accurate you need to be.
Is that distance supposed to be DRIVING distance or distance as
the missile flies?

Precomputing some of this can be used to advantage.

(1) You could precalculate the distance between every zip code and
every other zip code. This takes a lot of storage but it only has
to be computed once. You didn't say whether a zip code can be
characterized by its center or whether you have to take into account
whether any part of it is within the distance given.

(2) If the objective is to find the nearest store, or all stores
within N miles, where N has a small number of choices on a web page
(like 5, 10, 20, 50 miles), you can precalculate the distance between
each zip code WITH A STORE IN IT (and you could use the exact
lat/long of the store, not that of the zip code it's in, if you
know it) and each zip code where customers might be.

Make a table (store number, zip code (of CUSTOMER), distance) where
you drop any entries where the distance is unreasonably large or
much better alternatives exist. For example, you might leave in
an entry for a store 200 miles away if it's the closest one, but
drop it if there are 3 others within 10 miles of the customer. This
is a decision needed when constructing the table but you only have
to re-do it when you add/delete/move stores or if zip codes move
(they have been known to split, so the center moves).

You can also hand-tune recommendations (e.g. drop any that are close
but require the customer to travel through war zones, swim across
rivers where there aren't bridges, or over military artillery
practice areas. This requires a lot more detailed info than what
you've got, but someone familiar with the area around the store
might know this). Select on zip code matching and distance < the
radius the customer specified.

(3) You can try to simplify the calculation by converting the
coordinates to a linear grid (E-W and N-S from some point in the
middle of the area in question). This is terrible if you are trying
to do the entire USA (including Alaska and Hawaii) since the world
really isn't flat, but not too bad if you're trying to do a 100-mile
radius around some city, where the world is a reasonable approximation
to flat. Use a bounding box to limit the calculation. If you want
zip codes within 20 miles of (x,y), anything not within (x-21 ..
x+21, y-21 .. y+21) is DEFINITELY out, and you can use the more
precise calculation on the remaining candidates. Indexes on the
coordinates might help.

Gordon L. Burditt

[Philip Ronan]

Re: Zip code

"News" wrote:
[color=blue]
> Thanks. While waiting for an answer I did a similar thing to the above on
> my own. All I did was calculate the delta latitude and longitude
> (radius*360/24902) and added and subtracted from the center point. That
> gave the surrounding box. From there I will have not that many zipcodes. I
> can test each one for distance and see if it lies within the specified
> radius. That is the simplest method.[/color]

The delta longitude will be a bit different unless you're at the equator.
Off the top of my head, I'd say it's probably (radius*360/(24902*cos(lat) )

Rajesh's solution also looks good, BTW.

--
phil [dot] ronan @ virgin [dot] net

http://vzone.virgin.net/phil.ronan/

[News]

Re: Zip code


"Philip Ronan" <invalid@invali d.invalid> wrote in message
news:BF0EE186.3 577B%invalid@in valid.invalid.. .[color=blue]
> "News" wrote:
>[color=green]
>> Thanks. While waiting for an answer I did a similar thing to the above
>> on
>> my own. All I did was calculate the delta latitude and longitude
>> (radius*360/24902) and added and subtracted from the center point. That
>> gave the surrounding box. From there I will have not that many zipcodes.
>> I
>> can test each one for distance and see if it lies within the specified
>> radius. That is the simplest method.[/color]
>
> The delta longitude will be a bit different unless you're at the equator.
> Off the top of my head, I'd say it's probably (radius*360/(24902*cos(lat) )[/color]

Excellent point! Duh, I should have known that. After all, I teach Math.
Of course I will have to be careful with deg/rad. I will go no and look it
up.

Shelly

[Michael Phipps]

Re: Zip code

>I have a database of zipcodes with latitude and longitude. I also have the[color=blue]
>method of calculating the distance between two zipcodes. What I want to
>know is if there is an efficient algorithm for obtaining the zip codes
>within a specified distance of the first zipcode without having to retrieve
>and calculate for every record in the database.[/color]

How about a single select statement?

In this case I use a table called cities, where I have the fields city,
latitude and longitude. I have indexed the lat / long for improved speed.

$sqlstr="select city, ((acos(sin((lat itude)*(pi()/180)) *
sin((".$latitud e.")*(pi()/180)) + cos((latitude)* (pi()/180)) *
cos((".$latitud e.")*(pi()/180)) * cos((longitude -
".$longitude.") *(pi()/180))))*(180/pi())* 60 * 1.1515 * 1.609344) dist,
latitude, longitude from cities order by dist limit 30";

On my server this query returns results in under a second when the table is
indexed correctly.

This query is only returning the 30 closest cities to a latitude longitude,
but perhaps you can search where the dist is less than so many kilometers.

oh the *1.609344 at the end of the equation converts miles to kilometers.

I was originally thinking something much more complex was necessary, but it
isn't.

Hope it helps!

OH - where did you get the lat long database?

Michael

[Al Dykes]

Re: Zip code

In article <11ei85f8c660b4 9@corp.supernew s.com>,
Gordon Burditt <gordonb.haqjl@ burditt.org> wrote:[color=blue][color=green]
>>I have a database of zipcodes with latitude and longitude. I also have the
>>method of calculating the distance between two zipcodes. What I want to
>>know is if there is an efficient algorithm for obtaining the zip codes
>>within a specified distance of the first zipcode without having to retrieve
>>and calculate for every record in the database.[/color]
>
>It depends on what you are doing, and how accurate you need to be.
>Is that distance supposed to be DRIVING distance or distance as
>the missile flies?
>
>Precomputing some of this can be used to advantage.
>[/color]



have you looked at a zip code map for Manhattan?

--
a d y k e s @ p a n i x . c o m

Don't blame me. I voted for Gore.

[Gordon Burditt]

Re: Zip code

>>>I have a database of zipcodes with latitude and longitude. I also have the[color=blue][color=green][color=darkred]
>>>method of calculating the distance between two zipcodes. What I want to
>>>know is if there is an efficient algorithm for obtaining the zip codes
>>>within a specified distance of the first zipcode without having to retrieve
>>>and calculate for every record in the database.[/color]
>>
>>It depends on what you are doing, and how accurate you need to be.
>>Is that distance supposed to be DRIVING distance or distance as
>>the missile flies?
>>
>>Precomputin g some of this can be used to advantage.
>>[/color]
>
>
>
>have you looked at a zip code map for Manhattan?[/color]

Assuming for the moment that you have 100 stores, and you need to
compute the distance between the 100 stores and all the Zip codes
in Manhattan, and every (9 digit) Zip code that begins with 1 is
in Manhattan (this is a ridiculous over-estimate: Westchester
county contains 10510 and the far end of New York state contains
14092 (Lewiston), and that range of zip codes certainly covers
several states), and that it takes 1 millisecond to do a distance
calculation (with a 2-3 GHz processor with a floating point unit,
this should be easy), this calculation will take about 115 days.
But you only have to do it once.

Gordon L. Burditt

[Manuel Lemos]

Re: Zip code

Hello,

on 07/28/2005 09:28 AM News said the following:[color=blue]
> I have a database of zipcodes with latitude and longitude. I also have the
> method of calculating the distance between two zipcodes. What I want to
> know is if there is an efficient algorithm for obtaining the zip codes
> within a specified distance of the first zipcode without having to retrieve
> and calculate for every record in the database.[/color]

You may want to take a look at this class that is capable of computing a
range of latitude and longitude values to perform a distance search in
such way that it won't perform a full table scan (provide that you have
some indexes in place):

Class: Zip Codes Range

http://www.phpclasses.org/zipcodesrange

--

Regards,
Manuel Lemos

PHP Classes - Free ready to use OOP components written in PHP

http://www.phpclasses.org/

PHP Reviews - Reviews of PHP books and other products

http://www.phpclasses.org/reviews/

Metastorage - Data object relational mapping layer generator

http://www.meta-language.net/metastorage.html

[Positive Contrarian]

Re: Zip code

Here's one way (which I used in an air-defense application decades
ago):

Create a grid covering the geographic area under consideration, and for
each zipcode, compute the grid number in which its center exists, a
one-time task. (That grid number is retained as another field in the
database.)

Then, given an argument zip code, compute its grid number, and then
check against only that grid number and its eight (or 16, or 25)
surrounding grid neighbors. (Determining these neighbors is a bit
tricky, but ... .)

Grid configuration will depend on yr app's requirements.

AS