Simple Zip Code Perimeter Search in Rails

I recently finished up a feature that required a search to find all zip codes within a specified number of miles. I've worked with geo-coding before, but fortunately I was able to leave all the hard math to an already existing API (Google Maps, Yahoo Maps, etc.). However, for this project, we couldn't use an existing API and, fortunately, I found the math to be pretty simple.

There were several ways to approach this problem, all of them with varying degrees of complexity. The more complex the algorithm, the more accurate the search would be, but accuracy is also a trade-off for performance. I settled for the easiest and quickest route possible which is a simple box search.

Basically, with the box search, you take the geocode of your search zip code as the center point, convert the radius of your search into degrees latitude and longitude and then add/subtract degrees latitude and longitude to find the four corners of the container box. Once you have the four corners of the box represented in geocodes you can perform a simple search against your table of zip codes with their related geo codes to come up with a fairly accurate result set. (See example below)

There are 2 obvious problems with this search, one of which can be circumvented fairly easily in rails.

  1. The distance between the center point and any of the four corners of the surrounding box is greater than the specified radius of the search which will result in possible outliers in your search results. This is easily overcome by a simple where clause that calculates the distance of each zip code to the search zip code and weed out any that are further than the search radius.
  2. The other blaring problem with this approach is its simplistic geometry that doesn't take into account the curvature of the earth. However, for smaller radius searches, I've found this method to be pretty accurate.

Now for some code. Please excuse the line wrapping. I added a Search module in my Rails lib directory

module Search
  # ----------------------------------------------------------------------
  # returns a collection of zip codes that are within the specified
  # radius (in miles) of the given search zip code
  # ----------------------------------------------------------------------
  def zip_code_perimeter_search(zip, radius)
    #make sure we have valid parameters
    unless zip.blank? && radius.blank?
      #look up search zip_code in database
      zip_code = ZipCode.find_by_zip_code(zip)
      #make sure we found the zip code in the database first
      unless zip_code.nil?
        radius = radius.to_f  #convert radius to float
        latitude_miles = 69.172  #this is constant
        #longitude miles varies based on latitude, that is calculated here
        longitude_miles = (latitude_miles * 
                             Math.cos(zip_code.latitude * (Math::PI/180))).abs
        latitude_degrees = radius/latitude_miles  #radius in degrees latitude
        longitude_degrees = radius/longitude_miles  #radius in degrees longitude

        #now set min and max lat and long accordingly
        min_latitude = zip_code.latitude - latitude_degrees
        max_latitude = zip_code.latitude + latitude_degrees
        min_longitude = zip_code.longitude - longitude_degrees
        max_longitude = zip_code.longitude + longitude_degrees
        
        #now find all zip codes that are within 
        #these min/max lat/long bounds and return them
        #weed out any zip codes that fall outside of the search radius
        return ZipCode.find(:all,
              :select => "id, 
                          zip_code, 
                          latitude, 
                          longitude,  
                          sqrt( pow(#{latitude_miles} *
                                  (latitude-#{zip_code.latitude}),2) + 
                                pow(#{longitude_miles} * 
                                  (longitude-#{zip_code.longitude}),2)) 
                                as distance",
              :conditions => "(latitude BETWEEN #{min_latitude} 
                                AND #{max_latitude}) 
                              AND (longitude BETWEEN #{min_longitude} 
                                AND #{max_longitude}) 
                              AND sqrt(pow(#{latitude_miles} * 
                                (latitude-#{zip_code.latitude}),2) + 
                                pow(#{longitude_miles} * 
                                  (longitude-#{zip_code.longitude}),2)) 
                                <= #{radius}",
              :order => "distance")
      else
        return nil
      end
    else
      return nill
    end
  end
  
end

Then in your controller you can simply make the call like so...

zip_codes = zip_code_perimeter_search(params[:perimeter_zip_code], 
                         params[:perimeter_distance])

A list of zip codes can be downloaded for free from the U.S. Census Bureau here.

Comments

radius search

Pardon the noob question, but could you help me figure this out? Using your code in my RoR 1.8.6 project, I was getting "SQLite3::SQLException" error until I put spaces around the subtraction operator. It didn't like parsing negative longs and lats. Now I'm getting "no such function: pow". I've tried to substitute pow with Pow, POW, Math.pow and the ** operator, to no success.

I'm new to Ruby and SQL, so hopefully I've just overlooked something simple. Thanks in advance.

My find action looks like:

return Zipcode.find(:all,
:select => "zip, city, state, latitude, longitude, sqrt( pow(#{latitude_miles} * (latitude - #{zip_info.latitude}),2) + pow(#{longitude_miles} * (longitude - #{zip_info.longitude}),2)) as distance",
:conditions => "(latitude BETWEEN #{min_latitude} AND #{max_latitude}) AND (longitude BETWEEN #{min_longitude} AND #{max_longitude}) AND sqrt(pow(#{latitude_miles} * (latitude - #{zip_info.latitude}),2) + pow(#{longitude_miles} * (longitude - #{zip_info.longitude}),2)) <= #{radius}",
:order => "distance")