A Parallel Implementation of Douglas-Peucker Algorithm for Real-Time Map Generalization of Polyline Features on Multi-core Processor Computers

The Douglas-Peucker polyline simplification algorithm has been widely adopted in map generalization for decades,though it is often criticized for its low performance.As multi-core processor computers become widely available,it might be a good opportunity to improve the performance by converting its sequential implementation to parallel form.We present three different parallel implementations of the Douglas-Peucker algorithm.The first is in either recursive or non-recursive manner using OpenMP.The second is done by splitting a polyline feature into irrelevant segments and distributing segments to parallel threads.The third method is to dispatch 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 multi-core processor computers are compared among the three implementations together with the original sequential forms.We prove that with the increment of processor's cores and the number of threads accordingly,the parallel algorithms will efficiently reduce the number of vertex of a polyline and generate multi-resolution polyline data,which dramatically speed up the process of map generalization and thus real-time display effects are achieved.