exupero's blog
RSSApps

Great circle distance formulas

To calculate the distance between two points on a sphere, I've used the haversine formula, specifically this expression:

in which ψn denotes the latitude and λn the longitude of points on the sphere. Though Wikipedia provides derivation and proof of the formula's validity, it's still somewhat opaque, and every time I need it I have to look it up to remember the specifics.

An alternative approach is to convert latitude and longitude to Cartesian coordinates, then apply the geometric definition of dot product and the definition of radians:

Combining these equations into one produces this unweildy expression:

Superficially, that's less intelligible and harder to remember than the haversine formula, which by comparison is not only shorter but more symmetric.

Fortunately, we don't need a single equation. Executing the steps one at a time works just as well, and I'd argue better. The individual steps are more general and apply to a wider variety of situations, making them more worth committing to memory. Also, conversion of spherical to Cartesian coordinates can be extended to higher dimensions, which allows calculation of great circle distances on a hypersphere, an operation for which I have yet to find or derive an equivalent haversine-like formula (if you know of one, please email me).

Despite the clarity of the dot product approach, using the haversine formula is more computationally efficient. The more classical math I play with, the more I suspect that many of the arcane expressions we're used to weren't originally written for comprehension but instead for calculation, especially for computation by hand. For example, Wikipedia notes another haversine formula, which simplifies to:

The article notes that actual computation of that formula was eased by tables of haversine values. With reusable tables, the above calculation probably would have required about five lookups: three different haversine values, a square root, and an arcsine. Operations like converting to Cartesian coordinates and working out dot products may compose well, but it's hard to imagine what reusable tables could reduce the calculation to only five table lookups. I count four sine lookups, four cosine lookups, two square root lookups, and an arccosine lookup—eleven lookups, not to mention all the multiplication.

When computation was difficult, it made sense to do some extra work to find easier-to-calculate formulas, even if it obscured the underlying geometry. Most of the people doing such math historically didn't need to understand the geometry, just get an answer. Despite faster computation today, the same is still true, when computations may need to run millions or billions of times.

However, for instructive purposes, and for my own understanding, I prefer the composition of a few fundamentals to hundreds of efficient yet bespoke formulas.