A few days ago, I became painfully aware that the distance equation we all learn in geometry class, while it works perfectly well on flat, local projections,  is woefully inadequate when we’re talking about global coordinate systems.

In the midst of implementing Google Maps in our up-coming Sajara sample application, I realized that the International Date Line was causing problems. Large problems. Whenever the IDL was in play, I never retrieved the correct results from our database. One large problem was how we defined our bounding box inside Sajara itself. Once that was fixed, however, I realized that something was still wrong. The Nearest-to-Farthest sort was not behaving quite right: it was really doing a Nearest-on-this-side-of-the-IDL-first sort! The IDL was acting like a wall for our distance sort.

Example of linear distance with IDL in play. X = center of map

Here’s what we used before (in sql-speak):

RETURN sqrt(power(@FromX - @ToX,2) + power(@FromY - @ToY,2))

Your standard square-root of difference-squared plus difference-squared. This formula is fast and worked perfectly well so long as I operated under these two criteria:

1. a FLAT projection
2. POSITIVE numbers only

Once either of those things aren’t true anymore, I can’t use the basic distance formula. In my case, both things stopped being true at the same time! The solution? Something fairly math-magical to my mind, but accepted as THE formula to get at the distance between any two global coordinates: the Haversine Formula. Delving into descriptions of the formula brings up concepts such as spherical triangles, the planet’s elipticity, great circles and other things very important to navigation. It’s accurate down to about a meter, which is plenty for anything I’ll be doing with it.

Haversine Formula in Javascript:

var R = 6371; // radius of the earth
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad();
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) *
        Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var distance = R * c;

So here is the resulting SQL function that gives me the right distance between any two global coordinates.. basically a direct translation of the above javascript into T-SQL:

CREATE FUNCTION [dbo].[distance] (@FromX float, @FromY float, @ToX float, @ToY float)
RETURNS float AS BEGIN
DECLARE @R AS FLOAT;
SET @R = 6371;
DECLARE @DLAT AS FLOAT;
DECLARE @DLON AS FLOAT;
DECLARE @A AS FLOAT;
DECLARE @C AS FLOAT;
DECLARE @D AS FLOAT;
SET @DLAT = RADIANS(@ToY - @FromY);
SET @DLON = RADIANS(@ToX - @FromX);
SET @A =
SIN(@DLAT/2) * SIN(@DLAT/2) +
COS(RADIANS(@FromY)) * COS(RADIANS(@ToY)) * SIN(@DLON/2) * SIN(@DLON/2);
SET @C = 2 * ATN2(SQRT(@A), SQRT(1-@A));
SET @D = @R * @C;
RETURN @D
END