Sorting Latitude/Longitude Positions by Distance in SQL

Map Points

My recent project involved a database with lots of “location points” that were based on latitude and longitude. A user would be able to specify some pertinent information (such as address, state, or even county) and the location points would be displayed for the user. The results from this search came back in a relatively random order, but what we needed was  a way to sort our search results in relation to the center point in our map “view box”.

In our scenario, the end user would put in a basic search (address, zip code, county, etc.) into our form parameters and we’d send this to the Google Maps API to update our “view box.” Using the “box” coordinates generated by the API, we then would go into our own database to grab which location points were within the bounds of the view, dynamically put points on the map, and then display a list below the map that the user could interact with further. We wanted this list to be sorted according to the distance, which hadn’t been done before.

Fortunately, all of the hard work has been done, it is just a matter of piecing things together. When calculating distances, it is important to remember that the earth is a curve, so doing straight line comparisons don’t work. What you need to calculate is the haversine length between two points, which includes the curvature of the earth in this. There was a great overview of how to calculate haversine distances (as well as how to optimize it) in a presentation by one of the MySQL gurus.

Generally speaking, if you have a couple of variables (say MyLat and MyLon) and you have a table called “location” with the “lat” and “lon” columns accordingly, you’d query your locations and their distance with the following query:


SELECT *,

3956 * 2 * ASIN(SQRT(POWER(SIN((@MyLat - location.lat) * pi()/180 / 2), 2) + COS(@MyLat * pi()/180) * COS(location.lat * pi()/180) * POWER(SIN((@MyLon - location.lon) * pi()/180 / 2), 2))) AS Distance

The only glitch with this example to our scenario was that the examples relied upon a single point to calculate distance from. The scenario outlined in the examples were for showing the closest hotels from your location, or something similar. In our case, we were getting the Southwestern and Northeastern points in which we could display a box with for our view. What I needed to do was to find the midpoint of these two points, which would identify the center of our box and allow us to do the calculations with. Fortunately, Stack Overflow came to the rescue (yet again) and gave me a nice formula on finding the midpoint of two latitude/longitude coordinates. The answer was written in Java, but it was easy enough to convert to SQL code.

With all this in place, I was able to create the following stored procedure:


CREATE PROCEDURE [dbo].[GetLocations]
(
   @latsw float,
   @lonsw float,
   @latne float,
   @lonne float,
   @type nvarchar(20),
   @status nvarchar(7),
   @county nvarchar(20)
)
AS

BEGIN

SET NOCOUNT ON

DECLARE @dLon float
DECLARE @radLat1 float
DECLARE @radLon1 float
DECLARE @radLat2 float
DECLARE @radLon2 float
DECLARE @radMidLat float
DECLARE @radMidLon float
DECLARE @degMidLat float
DECLARE @degMidLon float
DECLARE @Bx float
DECLARE @By float

-- Since we are given the coordinates of the outer corner points of the
-- box, we need to calculate the midpoint of these coordinates in order
-- to do the proper distance calculation.
SET @dLon = RADIANS(@lonne - @lonsw)
SET @radLat1 = RADIANS(@latsw)
SET @radLon1 = RADIANS(@lonsw)
SET @radLat2 = RADIANS(@latne)
SET @radLon2 = RADIANS(@lonne)
SET @Bx = COS(@radLat1) * COS(@dLon)
SET @By = COS(@radLat2) * SIN(@dLon)
SET @radMidLat = ATN2(SIN(@radLat1) + SIN(@radLat2), SQRT((COS(@radLat1) + @Bx) * (COS(@radLat1) + @Bx) + @By * @By))
SET @radMidLon = @radLon1 + ATN2(@By, COS(@radLat1) + @Bx)
SET @degMidLat = DEGREES(@radMidLat)
SET @degMidLon = DEGREES(@radMidLon)

-- The distance is calculated from the midpoint using the haversine formula

SELECT [site_id],
       [site_name],
       [lat],
       [lon],
       [city],
       3956 * 2 * ASIN(SQRT(POWER(SIN((@degMidLat - sm_sites.lat) * pi()/180 / 2), 2) + COS(@degMidLat * pi()/180) * COS(sm_sites.lat * pi()/180) * POWER(SIN((@degMidLon- sm_sites.lon) * pi()/180 / 2), 2))) AS Distance

FROM [location]
     WHERE [Lat] BETWEEN @Latsw AND @LatNE
     AND
     [Lon] BETWEEN @LonSW AND @LonNE
ORDER BY Distance ASC

END

When I did a search on something with a small recordset that has records I have knowledge of (like Yavapai County), I got the following results back before the sort was in place:

No. Name                     City/State/Postal Code
1 Prescott Water District    Prescott Valley, AZ 86303
2 Quality Inn                Prescott, AZ 86301
3 Roadrunner Rentals         Camp Verde, AZ 86322
4 Davidsons                  Prescott, AZ 86301

Assuming we have the center of Yavapai county targetted (which we did) having Camp Verde in second to last wasn’ t accurate, it should have been the last, as well as our Prescott Valley reference.

After the sorting algorithm was put into place, our results were much more fine tuned:

No. Name                    City/State/Postal Code
1 Quality Inn               Prescott, AZ 86301 
2 Prescott Water District   Prescott Valley, AZ 86303
3 Davidsons                 Prescott, AZ 86301
4 Roadrunner Rentals        Camp Verde, AZ 86322

Notice how our Camp Verde entry is down at the end (as it should be) and we have some better sorting on our Prescott/Prescott Valley entries. Since Prescott is a little oddly shaped, there is a chance that we’d have a PV entry closer than from the center to another Prescott entry, which could be on the opposite end of town.

Hopefully this gives you some code to work with if you have to do your own geospatial calculations. The nice thing is that this can all be done in the database, so you can leverage its processing on that side of things. You may need to optimize your query more based on how many records your entire database has (ours is relatively small) but one of the “MySQL Guru” link will help you out with that.

About these ads

5 thoughts on “Sorting Latitude/Longitude Positions by Distance in SQL

What are your 10 bits on the matter? I want to know!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s