Finding Distance with Geocoded Data in TSQL

by Joe Finsterwald

This code sample applies to SQL Server 2000 and 2005. Examples are written in t-SQL.

The Problem
The Solution
Step 1: Constructing and Filling your Tables
Step 2: Convert from Degrees to Radians
Step 3: Define an Area and Retrieve a Subset Table
Step 4: Use the Law of Cosines to find points within the Subset
Step 5: Build a Stored Procedure and Put it all Together
View the Demo
Conclusion

The Problem:

You need to search a large number of geo-coded records by distance. Unfortunately, the point of origin for your calculation is not static. As a result, it is not possible to pre-calculate the information and write it to a table.

The solution:

The most elegant solution to this problem is to leverage the power of the database to do the heavy lifting for you. This problem has been solved in a myriad of ways on different sites, but I wasn't able to find a pure SQL solution so I decided to implement one. That said I'd like to give credit where credit is due. This article borrows heavily from an article by Mike Shaffer at the following URL: http://www.4guysfromrolla.com/webtech/010500-1.shtml.

This example uses a geo-coded zip code as the point of origin to derive a distance comparison between a large number of points in a database. The beauty of this method is that it leverages the set based logic of SQL to derive a subset of data before it begins calculating distance. I’ve also added in a unit conversion capability for purposes of internationalization.

Step 1: Constructing and Filling your Tables

I've include scripts to create and fill the two tables that I'm using for this example:

View the Schema

Step 2: Convert from Degrees To Radians

We need to build a utility function that will convert from degrees to radians because our algorithm is going to use trigonmeteric functions.

Click to View the Code

fnDegreesToRadians

CREATE       FUNCTION dbo.fnDegreesToRadians (@degree decimal(16, 12))
RETURNS decimal(16, 12) --@radian
AS
BEGIN
    DECLARE @radian decimal(16, 12)
    SELECT @radian = @degree * pi() / 180.0

    RETURN @radian
END

Step 3: Define an Area and Retrieve a Subset Table

Degrees latitude are uniformly the same distance apart from pole to pole. Each minute of latitude corresponds to one nautical mile. From this we can create a trapazoid whose area contains a subset of the geocoded points we are interested in. This will significantly speed our query.

Click to View the Code

fnGetAreaTable

CREATE     FUNCTION dbo.fnGetAreaTable (@zipCode varchar(5), 
    @radius int, @unit char(1))
RETURNS @areaResults TABLE(CustomerId    int,
    [Name]    varchar    (30),
    City    varchar    (255),
    State    char (2),
    Latitude    decimal    (16,12),
    Longitude    decimal (16,12))    
BEGIN
    
    DECLARE @iStartLat decimal(16, 12)
    DECLARE @iStartLong decimal(16, 12)

    SELECT
        @iStartLat = CAST(Latitude AS decimal(16, 12)), 
        @iStartLong = CAST(Longitude AS decimal(16, 12)) 
    FROM ZipCodes
    WHERE PostalCode = @zipCode
    
    DECLARE @latRange decimal(16, 12)
    DECLARE @longRange decimal(16, 12)
    
    IF (@unit = 'K')         --Get distance in kilometers
        BEGIN
            SELECT @LatRange = 
               (CAST(@radius / ((6076.0 / 5280.0) * 60.0) 
                AS decimal(16, 12))) * 0.621371
            SELECT @LongRange = 
               (@radius / (((cos(@iStartLat * pi() / 180.0) * 6076.0) 
                / 5280.0) * 60)) * 0.621371
        END
    ELSE                     --Get distance in miles (the default)
        BEGIN
            SELECT @LatRange = CAST(@radius / ((6076.0 / 5280.0) * 60.0) 
                AS decimal(16, 12))
            SELECT @LongRange = 
               @radius / (((cos(@iStartLat * pi() / 180.0) * 6076.0) 
                / 5280.0) * 60)
        END
    
    DECLARE @lowLatitude decimal(16, 12)
    DECLARE @highLatitude decimal(16, 12)
    DECLARE @lowLongitude decimal (16, 12)
    DECLARE @highLongitude decimal (16, 12)
    
    SELECT @lowLatitude = @iStartLat - @latRange
    SELECT @highLatitude = @iStartLat + @latRange
    SELECT @lowLongitude = @iStartLong - @longRange
    SELECT @highLongitude = @iStartLong + @longRange
     
    INSERT INTO @areaResults
    SELECT *
    FROM Customers C
    WHERE C.Latitude <= @highLatitude
        AND C.Latitude >= @lowLatitude
        AND C.Longitude >= @lowLongitude
        AND C.Longitude <= @highLongitude
    RETURN
END

Step 4: Use the Law of Cosines to find points within the Subset.

This function incorporate the Law of Cosines which allows us to find two points on the surface of a sphere.

Click to View the Code

fnGetDistance

CREATE        FUNCTION dbo.fnGetDistance (@zipCode varchar(5), 
    @lat2 decimal(16, 12), @long2 decimal(16, 12), @unit char(1))
RETURNS decimal(16, 12) --distance
AS
BEGIN
    DECLARE @lat1 decimal(16, 12)
    DECLARE @long1 decimal(16, 12)

    SELECT
        @lat1 = CAST(latitude AS decimal(16, 12)), 
        @long1 = CAST(longitude AS decimal(16, 12)) 
    FROM ZipCodes
    WHERE PostalCode = @zipCode

    DECLARE @result decimal(16, 12)
    DECLARE @x decimal(16, 12)
    
    --Law of Cosines
    SELECT @x = (sin(dbo.fnDegreesToRadians(@lat1)) * 
        sin(dbo.fnDegreesToRadians(@lat2)) + 
        cos(dbo.fnDegreesToRadians(@lat1)) * 
        cos(dbo.fnDegreesToRadians(@lat2)) * 
        cos(abs((dbo.fnDegreesToRadians(@long2)) - 
            (dbo.fnDegreesToRadians(@long1)))))
    
    --Get Acos(x)
    SELECT @x = atan((sqrt(1-square(@x)))/@x)
    
    --Unit conversions
    IF (@unit = 'K')         --Get distance in kilometers
        BEGIN
            SELECT @result = 1.852 * 60.0 * ((@x/pi())*180)
        END
    ELSE                     --Get distance in miles (the default)
        BEGIN
            SELECT @result = (1.852 * 60.0 * ((@x/pi())*180))/ 1.609344
        END
    
    RETURN @result
END

Step 5: Build a Stored Procedure and Put it all Together

I've written a stored procedure which calls the functions I've written in the preceding steps.

Click to View the Code

spZipCodeRadiusSearch

CREATE PROCEDURE spZipCodeRadiusSearch
(
    @zipcode     varchar(5),
    @radius        int,
    @unit        char(1) -- M for Miles, K for Kilometers: the default is 'M'
)
AS

BEGIN    
    SET NOCOUNT ON

    BEGIN
     IF (@unit = 'K') -- Distance KM
       BEGIN
           SELECT
               *,
               dbo.fnGetDistance(@zipcode, PT.latitude, PT.longitude, @unit) 
                   AS Distance_km
           FROM dbo.fnGetAreaTable(@zipcode, @radius, 'K') PT
           WHERE dbo.fnGetDistance(@zipcode, PT.latitude, 
               PT.longitude, 'K') <= @radius
           ORDER BY dbo.fnGetDistance(@zipcode, PT.latitude, PT.longitude, @unit) ASC
       END
     ELSE    -- Distance Miles
       BEGIN
           SELECT
               *,
               dbo.fnGetDistance(@zipcode, PT.latitude, 
                   PT.longitude, 'M') AS Distance_miles
           FROM dbo.fnGetAreaTable(@zipcode, @radius, 'M') PT
           WHERE dbo.fnGetDistance(@zipcode, PT.latitude, PT.longitude, @unit) <= @radius
           ORDER BY dbo.fnGetDistance(@zipcode, PT.latitude, PT.longitude, @unit) ASC
       END

      END
        DECLARE @err int
    SET @err = 0
        
    -- Check for sql server errors
    IF @err = -1
        BEGIN
              Raiserror('Parameter Error:Usage:exec ', 12, 1)
            RETURN @err
        END
    ELSE 
        BEGIN
            RETURN @@ERROR
        END
END

Conclusion:

Computing distances for large sets of data in a speedy way is easiest in the datalayer. Hopefully this example has demonstrated the power of TSQL when it comes to doing heavy computation on a large set of data.

Subject	Name	Date Submitted
Coreweb is AWESOME! You saved me many hours of work! Thanks for making this available. You example was really easy to follow! Great work! Reply View Thread	jean	9/25/2006 6:23:05 PM
Works great! Hi, Great solution! Thanks! Reply View Thread	Rick	10/7/2006 3:07:57 PM
sick! this article is amazing. thank you for your well-written UDFs + SP. i was able to plug it into my db with minor tweaking, and excellent results :) Reply View Thread	Trevor	8/8/2008 2:33:16 AM


* Name:		Email Address:
Include me on future newsletters or mailings. (Your email address will not be displayed or shared.)
* Subject:
* Message:
Please enter the code shown below. If you cannot read it, press "reset image" to generate a new one.
		* Enter code:

Finding Distance with Geocoded Data in TSQL

by Joe Finsterwald

Contents

The Problem:

The solution:

Step 1: Constructing and Filling your Tables

Step 2: Convert from Degrees To Radians

Step 3: Define an Area and Retrieve a Subset Table

Step 4: Use the Law of Cosines to find points within the Subset.

Step 5: Build a Stored Procedure and Put it all Together

Conclusion:

Comments

About the Author

Joseph Finsterwald

Other Articles by Joseph Finsterwald: