Monday, August 13, 2012 effengud software RSS Feed

Improving the “Calculating the Distance Between Cities” Algorithm

Improving the “Calculating the Distance Between Cities” Algorithm

This article serves as an addendum to my previous article entitled “Calculating the Distance Between Cities“. That article talked about finding the distance between cities as being a useful way to determine, for example, which of a company’s many locations might be closest to a particular customer.

In that example, your store database may consist of several dozen to several hundred records (one for each store), and for each record you would have to perform the distance calculation. This is not so bad. But what if you had over 1,000 locations? Or what if you wanted to find all cities located within a particular radius from a customer, regardless of whether or not you have a store there?

In this case, you would certainly NOT want to loop through all cities within your database making the distance calculation. That would take a VERY long time. You might, in a flash of inspiration, attempt to perform the distance calculation only for cities within that customer’s state… but that would not work very well for people who live near a state’s border, or for people who live, say, in Rhode Island.

This article details a method for dramatically reducing the amount of processing necessary to find all locations within a certain radius.

By first performing a rough trim of the cities list based on latitude and longitude, we limit the number of calculations we must make. By using the algorithm below, we can accomplish that, as well as ensure that we are grabbing all cities within a particular area, regardless of state boundaries, etc.

Given a customer’s latitude (iStartLat) and longitude (iStartLong), and the radius we wish to search (iRadius, in miles), the following algorithm will return the latitude and longitude range for cites we will evaluate (using the formula provided in the last article). NOTE: Be aware that — as in the last article — this algorithm is accurate enough for most e-commerce applications, but NOT for navigational applications:

iRadius = 150

LatRange = iradius / ((6076 / 5280) * 60)
LongRange = iRadius / (((cos(cdbl(iStartLat * _
3.141592653589 / 180)) * 6076.) / 5280.) * 60)

LowLatitude = istartlat – LatRange
HighLatitude = istartlat + LatRange
LowLongitude = istartlong – LongRange
HighLongitude = istartlong + LongRange

Now you can create a SQL statement which limits the recordset of cities in this manner:

FROM Locations
WHERE Latitude <= [HighLatitude]
AND Latitude >= [LowLatitude]
AND Longitude >= [LowLongitude]
AND Longitude <= [HighLongitude]

(Note: This algorithm works pretty well for US and Canadian cities. Adapting the algorithm to other regions may require changing the comparison order due to negative latitudes, etc.)

Performing the distance calculation (covered in the previous article) on the resulting recordset ensure that you are not wasting too many CPU cycles on cities that are obviously outside the radius you have specified.

Tags: , , ,