利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素  

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

作　　者：马劲松[1] 沈婕[2,3] 徐寿成[1] 

机构地区：[1]南京大学地理信息科学系,南京市汉口路22号210093 [2]南京师范大学地理科学学院,南京市文苑路1号210046 [3]南京师范大学虚拟地理环境教育部重点实验室,南京市文苑路1号210046

出　　处：《武汉大学学报（信息科学版）》2011年第12期1423-1426,1494,共5页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金资助项目(41071288)

摘　　要：Douglas-Peucker算法是线要素简化的经典算法,针对其存在大量计算、难以做到实时的缺点,运用并行技术实现Douglas-Peucker算法,并在多核处理器的计算机上进行实验,验证了并行算法的效率与实时性。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.

关 键 词：地图综合 DOUGLAS-PEUCKER算法 并行算法 多核处理器 串行算法 

分 类 号：P208[天文地球—地图制图学与地理信息工程]