单调链与二分法的Douglas-Peucker改进算法
|
摘要
针对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.
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.
引文
[1]朱晓波.顾及空间拓扑关系的多级河流矢量数据并行压缩方法研究[D].重庆:西南大学,2016.(ZHU Xiaobo.Research on parallel compression method for multilevel river linear vector data considering spatial topological relations[D].Chongqing:Southwest University,2016.)
[2]王进宝,刘正纲.曲线矢量数据压缩算法实现及评析[J].测绘与空间地理信息,2006,29(2):122-124.(WANG Jinbao,LIU Zhenggang.Implementation and analysis of curve vector data compression algorithm[J].Geomatics&Spatial Information Technology,2006,29(2):122-124.)
[3]于靖,陈刚,张笑,等.面向自然岸线抽稀的改进道格拉斯-普克算法[J].测绘科学,2015,40(4):23-27,33.(YU Jing,CHEN Gang,ZHANG Xiao,et al.An improved Douglas-Peucker algorithm oriented to natural shoreline simplification[J].Science of Surveying and Mapping,2015,40(4):23-27,33.)
[4]朱晓波,周廷刚,曾波,等.顾及空间邻接关系的多级河流线状矢量数据并行压缩算法[J].西南大学学报(自然科学版),2017,39(2):100-106.(ZHU Xiaobo,ZHOU Tinggang,ZENG Bo,et al.A parallel compression algorithm for multilevel river linear vector data considering spatial adjacency relations[J].Journal of Southwest(Natural Science Edition),2017,39(2):100-106.)
[5]张树凯,杨家轩,蔡垚,等.基于AIS航迹和DouglasPeucker算法的航线自动生成方法研究[J].重庆交通大学学报(自然科学版),2014,33(6):79-82,117.(ZHANG Shukai,YANG Jiaxuan,CAI Yao,et al.Automatic routing method based on AIS tracks and Douglas-Peucker[J].Journal of Chongqing Jiaotong University(Natural Science),2014,33(6):79-82,117.)
[6]刘民士,龙毅,费立凡.顾及拓扑一致性的水系三维曲线化简[J].测绘学报,2016,45(4):494-501.(LIU Minshi,LONG Yi,FEI Lifan.Line simplification of three-dimensional drainage considering topological consistency[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):494-501.)
[7]窦世卿,赵学胜,刘成军,等.河网线要素与DEM综合的三维Douglas-Peucker算法[J].测绘学报,2016,45(4):450-457.(DOU Shiqing,ZHAO Xuesheng,LIU Chengjun,et al.The three dimensional Douglas-Peucker algorithm for generalization between river network line element and DEM[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):450-457.)
[8]宋正祥,周晓光,陈律余.顾及拓扑与尖角的分类矢量数据分组压缩算法[J].测绘科学,2016,41(11):98-103.(SONG Zhengxiang,ZHOU Xiaoguang,CHEN Lüyü.A grouping compress algorithm of considering the topology andacute angle of classified vector data[J].Science of Surveying and Mapping,2016,41(11):98-103.)
[9]刘晓红,李树军.矢量数据压缩的角度分段道格拉斯算法研究[J].四川测绘,2005,28(2):51-52.(LIU Xiaohong,LI Shujun.Study on subsection Douglas algorithm with the goniometry in generalization[J].Surveying and Mapping of Sichuan,2005,28(2):51-52.)
[10]米学军,盛广铭,张婧,等.GIS中面积偏差控制下的矢量数据压缩算法[J].地理科学,2012,32(10):1236-1240.(MI Xuejun,SHENG Guangming,ZHANG Jing,et al.A new algorithm of vector date compression based on the tolerance of area error in GIS[J].Scientia Geographica Sinica,2012,32(10):1236-1240.)
[11]张传明,潘懋,吴焕萍,等.保持拓扑一致性的等高线化简算法研究[J].北京大学学报(自然科学版),2007,43(2):216-222.(ZHANG Chuanming,PAN Mao,WU Huanping,et al.Study on simplification of contour lines preserving topological coherence[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2007,43(2):216-222.)
[12]杨伟.GIS应用中的矢量数据压缩算法研究[D].成都:四川师范大学,2017.(YANG Wei.Research on compression algorithm for vector data in GIS[D].Chengdu:Sichuan Normal University,2017.)
[13]赵真,沈敬伟,谭诗腾.基于Douglas-Peucker的面状矢量数据压缩算法[J].测绘,2017,40(3):99-102.(ZHAO Zhen,SHEN Jingwei,TAN Shiteng.Surface vector data compression algorithm based on DouglasPeucker[J].Surveying and Mapping,2017,40(3):99-102.)
[14]WU S T,MARQUEZ M R G.A non-self-intersection Douglas-Peucker algorithm[C]∥16th Brazilian Symposium on Computer Graphics and Image Processing.Piscataway,New Jersey,USA:IEEE,2003:60-66.
[15]孙华,关丽华.基于二分法和辛普森法的冲模压力中心计算[J].模具制造,2017,17(10):31-33.(SUN Hua,GUAN Lihua.Calculation of die press center based on dichotomy and Simpson’s rule[J].Die&Mould Manufacture,2017,17(10):31-33.)
[16]完么才让.基于词典的藏语分词系统中顺序、索引和二分查找算法的性能比较[J].信息与电脑(理论版),2016(3):75-76.(WANMECAIRANG.Performance comparison of ordinal,index and binary search algorithm in dictionary-based Tibetan word segmentation system[J].China Computer&Communication,2016(3):75-76.)
[17]王旭芳.基于模式匹配和机器学习的协议识别技术研究[D].成都:电子科技大学,2014.(WANG Xufang.Research on protocol identification based on pattern matching and machine learning[D].Chengdu:School of Communication&Information Engineering,2014.)
[18]顾腾,陈晓勇,刘成强.一种Douglas-Peucker与Li-Openshaw结合改进的曲线化简方法[J].东华理工大学学报(自然科学版),2016,39(4):396-400.(GU Teng,CHEN Xiaoyong,LIU Chengqiang.A modified line simplification method combined Douglas-Peucker with Li-Openshaw[J].Journal of East China University of Technology(Natural Science),2016,39(4):396-400.)
[19]WHITE E R.Assessment of line-generalization algorithms using characteristic points[J].The American Cartographer,1985,12(1):17-28.
[20]李成名,郭沛沛,殷勇,等.一种顾及空间关系约束的线化简算法[J].测绘学报,2017,46(4):498-506.(LI Chengming,GUO Peipei,YIN Yong,et al.A line simplification algorithm considering spatial relations between two lines[J].Acta Geodaetica et Cartographica Sinica,2017,46(4):498-506.)
[21]MCMASTER R B.Automated line generalization[J].Cartographica,1987,24(2):74-111.
[22]武芳,朱鲲鹏.线要素化简算法几何精度评估[J].武汉大学学报(信息科学版),2008,33(6):600-603.(WU Fang,ZHU Kunpeng.Geometric accuracy assessment of linear features’simplification algorithms[J].Geomatics and Information Science of Wuhan University,2008,33(6):600-603.)
[23]陈竞男,钱海忠,王骁,等.提高线要素匹配率的动态化简方法[J].测绘学报,2016,45(4):486-493.(CHEN Jingnan,QIAN Haizhong,WANG Xiao,et al.Improving the matching rate of line feature by using dynamic simplification[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):486-493.)
[24]邓敏,陈杰,李志林,等.曲线简化中节点重要性度量方法比较及垂比弦法的改进[J].地理与地理信息科学,2009,25(1):40-43.(DENG Min,CHEN Jie,LI Zhilin,et al.An improved local measure method for the importance of vertices in curve simplification[J].Geography and Geo-Information Science,2009,25(1):40-43.)
[2]王进宝,刘正纲.曲线矢量数据压缩算法实现及评析[J].测绘与空间地理信息,2006,29(2):122-124.(WANG Jinbao,LIU Zhenggang.Implementation and analysis of curve vector data compression algorithm[J].Geomatics&Spatial Information Technology,2006,29(2):122-124.)
[3]于靖,陈刚,张笑,等.面向自然岸线抽稀的改进道格拉斯-普克算法[J].测绘科学,2015,40(4):23-27,33.(YU Jing,CHEN Gang,ZHANG Xiao,et al.An improved Douglas-Peucker algorithm oriented to natural shoreline simplification[J].Science of Surveying and Mapping,2015,40(4):23-27,33.)
[4]朱晓波,周廷刚,曾波,等.顾及空间邻接关系的多级河流线状矢量数据并行压缩算法[J].西南大学学报(自然科学版),2017,39(2):100-106.(ZHU Xiaobo,ZHOU Tinggang,ZENG Bo,et al.A parallel compression algorithm for multilevel river linear vector data considering spatial adjacency relations[J].Journal of Southwest(Natural Science Edition),2017,39(2):100-106.)
[5]张树凯,杨家轩,蔡垚,等.基于AIS航迹和DouglasPeucker算法的航线自动生成方法研究[J].重庆交通大学学报(自然科学版),2014,33(6):79-82,117.(ZHANG Shukai,YANG Jiaxuan,CAI Yao,et al.Automatic routing method based on AIS tracks and Douglas-Peucker[J].Journal of Chongqing Jiaotong University(Natural Science),2014,33(6):79-82,117.)
[6]刘民士,龙毅,费立凡.顾及拓扑一致性的水系三维曲线化简[J].测绘学报,2016,45(4):494-501.(LIU Minshi,LONG Yi,FEI Lifan.Line simplification of three-dimensional drainage considering topological consistency[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):494-501.)
[7]窦世卿,赵学胜,刘成军,等.河网线要素与DEM综合的三维Douglas-Peucker算法[J].测绘学报,2016,45(4):450-457.(DOU Shiqing,ZHAO Xuesheng,LIU Chengjun,et al.The three dimensional Douglas-Peucker algorithm for generalization between river network line element and DEM[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):450-457.)
[8]宋正祥,周晓光,陈律余.顾及拓扑与尖角的分类矢量数据分组压缩算法[J].测绘科学,2016,41(11):98-103.(SONG Zhengxiang,ZHOU Xiaoguang,CHEN Lüyü.A grouping compress algorithm of considering the topology andacute angle of classified vector data[J].Science of Surveying and Mapping,2016,41(11):98-103.)
[9]刘晓红,李树军.矢量数据压缩的角度分段道格拉斯算法研究[J].四川测绘,2005,28(2):51-52.(LIU Xiaohong,LI Shujun.Study on subsection Douglas algorithm with the goniometry in generalization[J].Surveying and Mapping of Sichuan,2005,28(2):51-52.)
[10]米学军,盛广铭,张婧,等.GIS中面积偏差控制下的矢量数据压缩算法[J].地理科学,2012,32(10):1236-1240.(MI Xuejun,SHENG Guangming,ZHANG Jing,et al.A new algorithm of vector date compression based on the tolerance of area error in GIS[J].Scientia Geographica Sinica,2012,32(10):1236-1240.)
[11]张传明,潘懋,吴焕萍,等.保持拓扑一致性的等高线化简算法研究[J].北京大学学报(自然科学版),2007,43(2):216-222.(ZHANG Chuanming,PAN Mao,WU Huanping,et al.Study on simplification of contour lines preserving topological coherence[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2007,43(2):216-222.)
[12]杨伟.GIS应用中的矢量数据压缩算法研究[D].成都:四川师范大学,2017.(YANG Wei.Research on compression algorithm for vector data in GIS[D].Chengdu:Sichuan Normal University,2017.)
[13]赵真,沈敬伟,谭诗腾.基于Douglas-Peucker的面状矢量数据压缩算法[J].测绘,2017,40(3):99-102.(ZHAO Zhen,SHEN Jingwei,TAN Shiteng.Surface vector data compression algorithm based on DouglasPeucker[J].Surveying and Mapping,2017,40(3):99-102.)
[14]WU S T,MARQUEZ M R G.A non-self-intersection Douglas-Peucker algorithm[C]∥16th Brazilian Symposium on Computer Graphics and Image Processing.Piscataway,New Jersey,USA:IEEE,2003:60-66.
[15]孙华,关丽华.基于二分法和辛普森法的冲模压力中心计算[J].模具制造,2017,17(10):31-33.(SUN Hua,GUAN Lihua.Calculation of die press center based on dichotomy and Simpson’s rule[J].Die&Mould Manufacture,2017,17(10):31-33.)
[16]完么才让.基于词典的藏语分词系统中顺序、索引和二分查找算法的性能比较[J].信息与电脑(理论版),2016(3):75-76.(WANMECAIRANG.Performance comparison of ordinal,index and binary search algorithm in dictionary-based Tibetan word segmentation system[J].China Computer&Communication,2016(3):75-76.)
[17]王旭芳.基于模式匹配和机器学习的协议识别技术研究[D].成都:电子科技大学,2014.(WANG Xufang.Research on protocol identification based on pattern matching and machine learning[D].Chengdu:School of Communication&Information Engineering,2014.)
[18]顾腾,陈晓勇,刘成强.一种Douglas-Peucker与Li-Openshaw结合改进的曲线化简方法[J].东华理工大学学报(自然科学版),2016,39(4):396-400.(GU Teng,CHEN Xiaoyong,LIU Chengqiang.A modified line simplification method combined Douglas-Peucker with Li-Openshaw[J].Journal of East China University of Technology(Natural Science),2016,39(4):396-400.)
[19]WHITE E R.Assessment of line-generalization algorithms using characteristic points[J].The American Cartographer,1985,12(1):17-28.
[20]李成名,郭沛沛,殷勇,等.一种顾及空间关系约束的线化简算法[J].测绘学报,2017,46(4):498-506.(LI Chengming,GUO Peipei,YIN Yong,et al.A line simplification algorithm considering spatial relations between two lines[J].Acta Geodaetica et Cartographica Sinica,2017,46(4):498-506.)
[21]MCMASTER R B.Automated line generalization[J].Cartographica,1987,24(2):74-111.
[22]武芳,朱鲲鹏.线要素化简算法几何精度评估[J].武汉大学学报(信息科学版),2008,33(6):600-603.(WU Fang,ZHU Kunpeng.Geometric accuracy assessment of linear features’simplification algorithms[J].Geomatics and Information Science of Wuhan University,2008,33(6):600-603.)
[23]陈竞男,钱海忠,王骁,等.提高线要素匹配率的动态化简方法[J].测绘学报,2016,45(4):486-493.(CHEN Jingnan,QIAN Haizhong,WANG Xiao,et al.Improving the matching rate of line feature by using dynamic simplification[J].Acta Geodaetica et Cartographica Sinica,2016,45(4):486-493.)
[24]邓敏,陈杰,李志林,等.曲线简化中节点重要性度量方法比较及垂比弦法的改进[J].地理与地理信息科学,2009,25(1):40-43.(DENG Min,CHEN Jie,LI Zhilin,et al.An improved local measure method for the importance of vertices in curve simplification[J].Geography and Geo-Information Science,2009,25(1):40-43.)