Geographic distance can be simple and fast

Suppose you are given the coordinates for two places on the globe and you want to know how far they are from each other. If you want to be precise this is actually quite hard because of the Earth’s irregular shape. If we model the Earth as a sphere the shortest path between two points is on a “large circle,” and you can compute the distance using the haversine formula or the spherical law of cosines. But these formulas are quite complicated and slow to compute, and the world is pretty flat over distances of a few kilometers. Surely there’s a fast approximation that’s good enough?

If the two points are near each other, for example in the same city, estimating the great circle with a straight line in the latitude-longitude space will produce minimal error, and be a lot faster to calculate. A minor complication is the fact that the length of a degree of longitude depends on the latitude: a degree of longitude spans 111km on the Equator, but half of that on 60° north. Adjusting for this is easy: multiply the longitude by the cosine of the latitude. Then you can just take the Euclidean distance between the two points, and multiply by the length of a degree:

distance(lat, lng, lat0, lng0):
    deglen := 110.25
    x := lat - lat0
    y := (lng - lng0)*cos(lat0)
    return deglen*sqrt(x*x + y*y)

If you work in SQL, and don’t have spatial geometry primitives, you can apply this snippet to find points that are less than $d km from a given ($lat, $lng) pair:

select lat, lng from points where 
pow(lat-$lat, 2) + pow((lng-$lng)*cos(radians($lat)), 2) < pow($d/110.25, 2)

Can we make it even faster? Sure: you might precompute the cosines when the data first arrives. Also, small errors when computing the cosine don’t matter much, so we can replace it with a table lookup or a polynomial approximation.

Cute. But how bad is the error?

When making approximations it’s important to keep in mind how much error you are introducing. If you don’t care about the error, why not just say that the distance between any two points is 5km?

I won’t do a detailed error analysis because the formulas involved in spherical geometry are long, boring, and easy to get wrong. Since the error is worst near the poles, plotting the error made around some points will give us an idea of how bad the error can be. This is a plot of the relative error made over a 5km distance at 89° degrees north, and again at 65° degrees north:

Relative error made

Relative error made over 5km in two points. A circle with 5km radius for reference. (source code)

The location for the first plot is completely unrealistic of course: 89° is about 110km from the pole. No permanent human settlements lie that near to a pole, unless you count Antarctic research stations. And yet the relative error is less than 1% for distances less than 5km. The second plot shows relative error is less than 0.04% for distances less than 5km at 65°. That’s not far from the polar circle.

What about longer distances, like 50km?

Relative error made over 50km

Relative error made over 50km in two points. A circle with 50km radius for reference.

This plot shows that the error at 89° is now a lot bigger: over 10%. This could be expected: the northernmost point of the 50km circle is only about 60km from the pole, so the assumptions made by the approximation are breaking. The circle doesn’t even look like one in the latitude-longitude space. At 65° however the error still stays manageable: less than 0.4%.

The error made by modeling the Earth as a sphere is cited to be larger than 0.5%, so the method for approximate distance derived here is just as good as the Haversine formula, but a lot simpler to compute.