What pre-existing services exist for calculating distance between two addresses?

Question

I'd like to implement a way to display a list of stored addresses sorted by proximity to a given address.

Addresses in the list will be stored in a database table. Separate parts have separate fields (we have fields for postal code, city name, etc.) so it is not just a giant varchar. These are user-entered and due to the nature of the system may not always be complete (some may be missing postal code and others may have little more than city and state).

Though this is for an intranet application I have no problems using outside resources including accessing internet web services and such. I'd actually prefer that over rolling my own unless it would be trivial to do myself. If Google or Yahoo! already provides a free service, I'm more than willing to check it out. The keyword is it must be free, as I'm not at liberty to introduce any additional cost onto this project for this feature as it is already a bonus "perk" so to speak.

I'm thinking of this much like many brick & mortar shops do their "Find a Location" feature. Showing it in a simple table sorted appropriately and displaying distance (in, say, miles) is great. Showing a map mash-up is even cooler, but I can definitely live with just getting the distance back and me handling all of the subsequent display and sorting.

The problem with simple distance algorithms is the nature of the data. Since all or part of the address can be undefined, I don't have anything convenient like lat/long coords. Also, even if I make postal codes required, 90% of the addresses will probably have the same five postal codes.

While it need not be blisteringly fast, anything that takes more than seven seconds to show up on the page due to latency might be too long for the average user to wait, as we know. If such a hypothetical service supports sending a batch of addresses at once instead of querying one at a time, that'd be great. Still, I should not think the list of addresses would exceed 50 total, if that many.

Answer 1

Google and Yahoo! both provide geocoding services for free. You can calculate distance using the Haversine formula (implemented in .NET or SQL). Both services will let you do partial searches (zip code only, city only) and will let you know what the precision of their results are (so that you can exclude locations without meaningful information, though Yahoo! provides more precision info than Google).

Answer 2

The Google Maps API is no good to you due to their terms of use. However, Yahoo offer a REST service for turning addresses into Long/Lat coordinates, which you could then use to calculate distances. Its here.

Answer 3

Require them to enter a ZIP code, then create a database table mapping ZIP code to latitude/longitude pairs (or find one online). I don't know how it is where you work but over here, ZIP code can be specific to several meters, so that should be precise enough. Then use this method to calculate the distance between two ZIP codes:

public static double distance(double lat1, double lon1, double lat2, double lon2, char unit)
{
  double theta = lon1 - lon2;
  double dist = Math.Sin(deg2rad(lat1)) * Math.Sin(deg2rad(lat2)) +
    Math.Cos(deg2rad(lat1)) * Math.Cos(deg2rad(lat2)) * Math.Cos(deg2rad(theta));
  dist = Math.Acos(dist);
  dist = rad2deg(dist);
  dist = dist * 60 * 1.1515;
  if (unit == 'K')
  {
    dist = dist * 1.609344;
  }
  else if (unit == 'N')
  {
    dist = dist * 0.8684;
  }
  return (dist);
}

private static double deg2rad(double deg)
{
  return (deg * Math.PI / 180.0);
}

private static double rad2deg(double rad)
{
  return (rad / Math.PI * 180.0);
}

The advantage of using your own code over a geocoding service is that you can then do a bunch more interesting calculations against the data as well as storing stuff alongside it in your db.

Answer 4

Can't you just use google maps API to get the distances and sort them on your side?

http://code.google.com/apis/maps/