Task: Geocode events and provide a "show me events within n miles of this ZIP"
query

1. Geocoding events.

For non-profit purposes you can use the geocoder.us XML-RPC web service. You
can find an example client, written in Perl, at:

	http://geocoder.us/dist/eg/clients/xmlrpc.pl

I will assume that the events will be stored in an SQL table called "event" and
that the latitude and longitude will be stored in float columns called "lat"
and "lon" respectively.

Some things you need to be prepared for: First, sometimes the geocoder
returns multiple hits for an address, such as when there's both a North and
South Main Street but neither one was specified. Second, sometimes the
geocoder just can't parse or can't find an address. In that event, I
recommend storing the latitude and longitude of the matching ZIP code
centroid from the database below as a fallback.

2. Import a ZIP code centroid database.

You can get the database I built for CivicSpace from:

  http://civicspacelabs.org/releases/zipcodes/zipcodes-mysql-10-Aug-2004.tgz

This is a MySQL dump that will import directly into your database. The
database schema looks like this:

	CREATE TABLE zipcodes (
	  zip int(5) NOT NULL default '0',
	  city varchar(30) NOT NULL default '',
	  state char(2) NOT NULL default '',
	  latitude decimal(10,6) NOT NULL default '0.000000',
	  longitude decimal(10,6) NOT NULL default '0.000000',
	  timezone tinyint(2) NOT NULL default '0',
	  dst tinyint(1) NOT NULL default '0',
	  PRIMARY KEY  (zip)
	);

So far, so good.

3. Perform distance queries.

Suppose we want to find events within 20 miles of zipcode 94110.  First,
select latitude, longtiude from zipcode and put the results in $zlat and
$zlon. Then compute the bounding box:

	$maxdist = 20;
	$deg2rad = 4 * atan(1,1) / 180; # PI / 180
	$boxlat = $maxdist / 69.0468;
	$boxlon = $boxlat * cos( ($zlat - $boxlat / 2) * $deg2rad );

Now, perform your bounding box query against the event table:

	select * from event
	    where abs(lat - $zlat) <= $boxlat
	    and	  abs(lon - $zlon) <= $boxlon;

Now, the results you get back are not guaranteed to be within a 20 mile
radius, because we selected a box and not a circle. So, supposing your
results are in @events, you can filter them to find out which ones end up
inside the radius in Perl as follows:

    my $radius = 3956.4538; # miles
    my $lat0 = (90 - $zlat) * $deg2rad;
    my @wanted;

    for my $e (@events) {
	my $lat1 = (90 - $e->{lat})    * $deg2rad;
	my $dlon = ($zlon - $e->{lon}) * $deg2rad;
	$e->{dist} = $radius * acos(
	    cos( $lat0 ) * cos( $lat1 ) * cos( $dlon ) +
            sin( $lat0 ) * sin( $lat1 ) );
	push @wanted, $e if $e->{dist} < $maxdist;
    }

Each item in @wanted now has a "dist" property containing its distance from
the ZIP code centroid in miles.  The conversion to PHP should be
straightforward.

4. Find the n closest events to a particular ZIP code.

This is a little trickier, because we can't just compute a bounding box.
Suppose we want the 10 closest events to ZIP code 94110 and we already have
the $zlat and $zlon.

    select *, pow(lat - $zlat, 2) + pow(lon - $zlon, 2) as dist
	from event
	order by dist asc
	limit 10;

This is a little rough, because it uses rectangular distance with spherical
coordinates, but it should work for most purposes, and it should be
reasonably efficient until the event table grows quite large.  Once you get
the rows back, you can filter them as described above to obtain the actual
distance in miles.

-- Schuyler Erle <schuyler@nocat.net>
27 October 2004

= 30 =