2019 FOSS4G Bucharest Talks speaker: Vissarion Fisikopoulos
Geodesic algorithms: an experimental study
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.
- 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
Geographic measures in Boost Geometry: length, area and beyond
How to compute the two closest points between two administrative units in a city and how this differs from distance computation? What happens when some points are on opposite/antipodal sides of the globe? How can one create equidistant points along a trajectory modelled by line segments?
We discuss solutions to those questions highlighting some of the latest developments in Boost Geometry, the library that is currently being used to provide GIS support to MySQL. The implemented algorithms are parameterized by strategies that control the accuracy-efficiency trade-off. The proposed solutions work for 3 different coordinate systems (namely, cartesian, spherical and ellipsoidal) each of which comes with its own advantages and limitations. Those are illustrated and supported by benchmarks.
The presentation is example driven thus emphasizing on the user perspective while glancing at the algorithmic and implementation aspects of the library.