The figure of the Earth can be modelled either by a cartesian plane, a sphere or an (oblate) ellipsoid, in decreasing order with respect to the approximation quality. The shortest path between two points on such a surface is called a geodesic. Studying geodesic problems on ellipsoids dates back to Newton. However, the majority of open-source GIS systems today use methods on the cartesian plane. The main advantages of those approaches are simplicity of implementation and performance. On the other hand, those approaches come with a handicap: accuracy.
We experimentally study the accuracy-performance trade-offs of various methods for distance computation (as well as similar geodesic problems such as azimuth and area computation). We test projections paired with cartesian computations, spherical-trigonometric computations and a number of ellipsoidal methods such as [Andoyer'65] and [Thomas'70] formulas, [Vincenty'75] iterative method, great elliptic arc's method, and [Karney'15] series approximation. We also show that some methods from the bibliography (e.g. [Tseng'15]) are neither faster nor more accurate compared to the above list of methods and thus become redundant. For our experiments we use the open source libraries Boost Geometry and GeographicLib.
Our results are of independent interest since we are not aware of a similar experimental study. More interestingly, they can be used as a reference for practitioners that want to use the most efficient method with respect to some given accuracy.
Geodesic computations (such as distance computations) apart from being a fundamental problem in computational geometry and geography/geodesy are also building blocks for many higher level algorithms such as k-nearest neighbour problems, line interpolation, densification of geometries, area and buffer, to name a few.
# References
* Some experimental results can be found here: https://github.com/vissarion/geometry/wiki/Accuracy-and-performance-of-geographic-algorithms
* A related talk (with some graphs on performance and accuracy) can be found here https://fosdem.org/2019/schedule/event/geo_boostgeometry
* The source code of most of the algorithms of the study is in Boost Geometry: https://github.com/boostorg/geometry but we contain to our study GeographicLib https://geographiclib.sourceforge.io
None