|
|
Posted by Philip Ronan on 10/23/73 11:22
"News" wrote:
> 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
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/
Navigation:
[Reply to this message]
|