A real-time parallel implementation of Douglas-Peucker polyline simplification algorithm on shared memory multi-core processor computers

摘要

GIS software requires the ability to simplify polyline features in real-time when displaying linear vector data with plenty of vertices. The Douglas-Peucker polyline simplification algorithm has been widely adopted in this area for decades, though it is often criticized for its low performance when exist a large number of vertices on a polyline which should be subdivided into many separate segments and calculated perpendicular offsets repeatedly in the algorithm. That was the main obstacle to accomplish real-time simplification and displaying. As shared memory multi-core processor computers become more widely available, it might be a good opportunity to improve the performance of the Douglas-Peucker method by converting its sequential implementation to parallel form. This paper presents two different parallel implementations. The first is done by separating a polyline feature into irrelevant segments and distributing segments to parallel threads. The second dispatches each polyline feature to an idle parallel thread in which the conventional sequential method is applied. By utilizing the official China's provincial boundary geospatial data set, and C++ language for programming, performances on various shared memory multi-core processor computers (including dual-core, triple-core, and quad-core processors from AMD and Intel respectively) are compared among the four implementations together with the original sequential forms. It is proved that with the increment of processor's cores and the number of threads accordingly, the parallel algorithms will efficiently reduce the number of vertices of a polyline and generate multi-resolution polyline data, which will dramatically speed up the process of simplifications and thus real-time display effects are achieved.