Zipcodes & Distance

Question

Hi,

I have a list of zipcoded in a MySQL Database together with their Latitude & Longitude data (Column names: ZipCode, Lat, Lon).

Now I have to make a search requests (search for the zipcode) to extract information from a website. When I make this search requests the results include all information within a radius of 50km of the zipcode.

Now, I don't want to make an unnessary high amount of search requests, so I would like to minimize the amount of zipcodes. So I'm looking for a way to filter all zipcodes, so that I have only the zipcodes where the distance between them is >50km.

Unfortunately I have no idea how to to it. Can someone help me to solve this?

Answer 1

You can use the google geocoding api , it allows you to get distances between 2 locations (lat/long, it also allows you to get zip from lat/long). From this you should be able to get the distance between each of your zipcodes and put them into a table, then you can do searches on just these.

Answer 2

You may be interested in checking out the following presentation:

• Geo/Spatial Search with MySQL by Alexander Rubin

The author describes how you can use the Haversine Formula in MySQL to limit your searches to a defined range. He also describes how to avoid a full table scan for such queries, using traditional indexes on the latitude and longitude columns.

Answer 3

Well, I see no other way then to iterate all rows on each request and filter them by calculating distance between selected zipcode and others (all of them), based on Lat & Lon.

I am using something similiar... http://webarto.com/googlemaps http://webarto.com/izrada-web-stranica/belgrade

PHP function for distance between two LL...

function distance($lat1, $lon1, $lat2, $lon2){ 
  $theta = $lon1 - $lon2; 
  $dist = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) +  cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($theta)); 
  $dist = acos($dist); 
  $dist = rad2deg($dist); 
  $miles = $dist * 60 * 1.1515;
  return round($miles * 1.609344,3);
}

I calculate it this way...

$sql = mysql_query("SELECT * FROM geoip WHERE city = '$city'");
while($row = mysql_fetch_array($sql)){
    $ll = explode(",",$row["ll"]);
    $x = distance(44.5428009033,18.6693992615,$ll[0],$ll[1]);
    $road = intval($x+($x/3));

    echo "Distance between ".$row["city"]." and Tuzla is ".$x." kilometers of airline, that's about ".$road." kilometers of road way.";
}

Answer 4

Daniel's link deals with selecting all the zip codes within 50km of a given latitude/longitude. Once you can do that, you can build a filtered list of zipcodes like this...

1. Select a zip code at random and add it to the filtered list
2. Delete all zip codes which lie within 50km of the selected zip code
3. Select a new zip code at random from the remaining zip codes, repeat until no more are left.

You know that you're only picking zip codes that are >50km from the ones already picked, and you know that once the original table is empty it must be because all zip codes lie within 50km of at least one of your selected zip codes.

That doesn't guarantee the smallest possible list of zip codes, and the size of the result will depend on the random choices. However, I think that this simple algorithm is likely to be "good enough", and that saving a few searches wouldn't justify the extra effort involved in finding a truly optimal solution.

Answer 5

The problem has been discussed previously here on SO with various solutions