Monthly Archive for March, 2009

Radius-based Zip Code Finder

Published on March 12, 2009 in Applications. 3 Comments

A year or so ago, I had the task to build a “zip code finder”; a tool that allows a user to enter a zip code and a radius, and return all zip codes in that radius.  All of the references I found online were pretty much the exact application I was trying to build, so they didn’t help me that much. I did eventually run across the math that allows you to build the application. Unfortunately, I didn’t save the link to the page. If I ever find it, I’ll be sure to post it. While I initially built this application for US zip codes, I’m sure it’ll work for zip codes outside of the US, since we are mostly concerned with the longitude and latitudes of the zip codes. This is how to build a radius-based zip code finder:

First, you need a zip code database. The database should contain the following fields at minimum: zip code, longitude, and latitude. Let me say that this task alone can be difficult, if you are searching for a free database. Most of the databases available will cost money, mainly because the database data changes every-so often (since US zip codes change every so often). Free databases (mostly in the form of a .CSV file) are out there, but if you want a highly accurate database, it might be worth to pay the money for one.

Update – After looking around for a little bit, I found this file that will work as a nice zip code database. The file comes directly from the US Census, so it should be pretty accurate. You can also check this SourceForge project for a nice zip code database.

Now comes the math and the process of determining the longitudes and latitudes in the radius. Since I’m not a math expert, I’ll do my best to explain what each number or formula is. For the formulas, I’ll show the PHP code (I actually created the PHP code by converting the original .NET code I wrote.)

Step 1
Find the longitude and latitude for the zip code using the database. This is your center point for your radius. If you can’t find the zip code in the database, then the zip code is incorrect or you have an outdated database.

Step 2
Convert the longitude, latitude, and radius distance (in miles) to radians using these formulas:

1
2
3
4

// Convert the coordinates and distance to radians
$dLatInRads = $latitude * (M_PI / 180);
$dLongInRads = $longitude * (M_PI / 180);
$dDistInRad = $distanceRadius / EARTH_RADIUS_IN_MILES;

EARTH_RADIUS_IN_MILES is a constant set to 3956. M_PI is a PHP constant.

Step 3
Honestly, I don’t remember what this number is for. In my code, it’s called “lat”. It uses this formula:

1

$lat = asin(sin($dLatInRads) * cos($dDistInRad));

Step 4
Find the top and bottom lines of the bounding box using this formula:

1
2
3
4
5
6
7

// Find the top line
$topLine = $dLatInRads + $dDistInRad;
$topLine *= (180 / M_PI);
 
// Find the bottom line
$bottomLine = $dLatInRads - $dDistInRad;
$bottomLine *= (180 / M_PI);

Step 5
Find the right and left lines of the bounding box. For each line, you need to calculate a number called “dlon”. Once again, I don’t remember what this is. Here is the formula:

1
2
3
4
5
6
7
8
9

// Find the right line
$dlon = atan2(sin(M_PI / 2) * sin($dDistInRad) * cos($dLatInRads), cos($dDistInRad) - sin($dLatInRads) * sin($lat));
$rightLine = (fmod(($dLongInRads + $dlon + M_PI), (2 * M_PI))) - M_PI;
$rightLine *= (180 / M_PI);
 
// Find the left line
$dlon = atan2(sin(3 * M_PI / 2) * sin($dDistInRad) * cos($dLatInRads), cos($dDistInRad) - sin($dLatInRads) * sin($lat));
$leftLine = (fmod(($dLongInRads + $dlon + M_PI), (2 * M_PI))) - M_PI;
$leftLine *= (180 / M_PI);

You now have the full bounding box of the zip code radius.

Step 6
Using the database, find all longitudes and latitudes in the bounding box. I use this SQL statement:

1
2
3
4
5
6

SELECT ZipCode, Latitude, Longitude
FROM ZipCodes
WHERE Latitude <= '$bottomLine'
AND Latitude >= '$topLine'
AND Longitude <= '$leftLine'
AND Longitude >= '$rightLine'";

This will return all the zip codes in the bounding box. Note that the bounding box is exactly that… a box. Some of the zip codes you return will be outside of the initial radius. If you want, you can filter out those zip codes in Step 7.

Step 7 (optional)
Filter out the zip codes outside of the radius by simply checking the distance between the center longitude/latitude and the returned zip code longitude/latitude. Use this formula:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Convert all the coordinates to radians
$dStartLatInRad = $startLatitude * (M_PI / 180);
$dStartLongInRad = $startLongitude * (M_PI / 180);
$dEndLatInRad = $endLatitude * (M_PI / 180);
$dEndLongInRad = $endLongitude * (M_PI / 180);
 
// Find the distance between the starting and ending coordinates
$dLatitude = $dEndLatInRad - $dStartLatInRad;
$dLongitude = $dEndLongInRad - $dStartLongInRad;
 
// Intermediate result a
$a = pow(sin($dLatitude / 2) , 2) + cos($dStartLatInRad) * cos($dEndLatInRad) * pow(sin($dLongitude / 2), 2);
 
// Intermediate result c (great circle distance in radians)
$c = 2 * atan2(sqrt($a), sqrt(1 - $a));
 
// Distance
$dDistance = EARTH_RADIUS_IN_MILES * $c;

After you filter out the zip codes, you can return your result set. That’s it!