Robust line simplification on the surface of the sphere

Polyline simplification is an important task in map generalization. Several solutions have been developed in order to perform this task automatically, but the vast majority of them consider that the objective line to simplify is lying on the plane. One of the most widely used methods is the so-called Douglas-Peucker algorithm, which is fast and in most cases produces good results. However, the Douglas-Peucker method was defined in its original form in order to be applied to polylines contained in the Euclidean 2D space, and it can lead to inconsistent results such as self-intersections. In this work, a robust (results without self-intersections) variation of the Douglas-Peucker for polylines on the surface of the sphere is presented. It produces correct results regardless of the morphology of the original line and the tolerance parameter size.The algorithm is coded in standard C99 and it can be compiled for serial or parallel execution via OpenMP. Both, the algorithm itself and a program implementing it are distributed as free software. The solution validity was tested using the GSHHG geography database, which can be obtained free through the Web. Results about output accuracy, execution speed, and parallel implementation scalability are presented. HighlightsA robust method for line simplification on the surface of the sphere is presented.The method is based in the well known Douglas-Peucker algorithm.The method can be implemented as a serial or parallel algorithm.Tests were made using the public domain GSHHG coastline database.Tests were made in order to see the behaviour in shared memory environments.