单调链与二分法的Douglas-Peucker改进算法  

An improved Douglas-Peucker algorithm based on monotonic chain and binary search method

作　　者：刘波[1] 刘雪朝 刘鸿剑 罗文奇 刘斌[1] 胡玮祺 吴静[1] LIU Bo;LIU Xuechao;LIU Hongjian;LUO Wenqi;LIU Bin;HU Weiqi;WU Jing(East China University of Technology/Key Laboratory of Watershed Ecology and Geographical Environment Monitoring,National Administration of Surveying,Mapping and Geoinformation, Nanchang 330013,China;China Energy Engineering Group Gansu Electric Power Design Institute Co.,Ltd.,Lanzhou730050,China)

机构地区：[1]东华理工大学/流域生态与地理环境监测国家测绘地理信息局重点实验室,南昌330013 [2]中国能源建设集团甘肃省电力设计院有限公司,兰州730050

出　　处：《测绘科学》2019年第2期50-55,共6页Science of Surveying and Mapping

基　　金：国家自然科学基金项目(41201395;41601416);流域生态与地理环境监测国家测绘地理信息局重点实验室开放基金项目(WE2015011);江西省教改课题项目(JXJG-16-6-10)

摘　　要：针对Douglas-Peucker(D-P)算法对一些较复杂的曲线进行压缩时易产生自相交等错误,阻碍其在数据压缩方面的应用的问题,该文基于单调链与二分法,对D-P算法进行改进。该方法首先利用D-P算法对复杂曲线进行压缩,并将压缩后的曲线分成若干单调链;其次利用二分法对相交的单调链进行快速精确定位,并对相交的单调链进行处理,从而解决自相交问题。通过实验验证,在处理矢量数据压缩中自相交的问题时,改进的D-P算法在算法效率、压缩率和算法精度等方面都具有较好的效果。Aiming at the problem that it’s easy to generate self-intersecting errors when using the Douglas-Peucker(D-P)algorithm to compress some complex curves,which prevented the applications of D-P algorithm in data compression,an improved D-P algorithm which based on monotone chains and binary search method was proposed in this paper.Firstly the D-P algorithm was used to compress the complex curve,and then the compressed curve was divided into several monotone chains.Secondly,the binary search method was used to fast search the intersecting positions of monotone chains,and the intersecting monotone chains were processed,thus the self-intersection problems were solved.Through the experimental verification,when the vector data were compressed,it was effective for the improved D-P algorithm in algorithm efficiency,compression ratio and algorithm accuracy,to deal with the selfintersection problems.

关 键 词：单调链 二分法 DOUGLAS-PEUCKER算法 矢量数据压缩 

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