顾及三维形态特征的河流曲线化简方法
|
摘要
鉴于常规曲线化简方法应用于河流曲线化简时难以顾及河流要素的三维特征及其拓扑结构,提出了一种顾及三维形态特征的河流曲线化简方法。该方法利用河流曲线上散点的三维特征对散点进行选取进而实现河流曲线化简。在三维Douglas-Peucker(3D D-P)算法的基础上提出一种三维散点排队法,根据散点的三维特征对河流曲线的离散点集进行排队,并通过初始排队、"3合1"队列合并及约束点位置调整3个过程建立散点队列,然后根据压缩比从队列尾部删除相应比例的点数获得散点综合结果,将综合后的散点按照河流曲线的原始次序重构出化简后的河流曲线。实验结果表明,该方法既能最大程度地保留河流的三维形态特征,又能保证河流曲线之间的拓扑结构一致性。
In view of routine line simplification method less considering river curve's three-dimensional shape and topological structure which is applied to line simplification of river,the paper proposes a method of river line simplification considering three-dimensional shape characteristics.On the basis of three-dimensional Douglas-Peucker(3D D-P)algorithm,a three-dimensional scatter point queuing method is proposed.In this algorithm,points set in river curves are queued by river curves' three-dimensional feature,which would be divided into initial queue process,"3 in 1"combination queue process and adjusting constraint point position process.Then,some proportional points corresponding with compression ratio are deleted from queue's rear.Finally,simplified river curves are reconstructed by points' order in river curve.The results of experiment show that river curves' three-dimensional shape feature could be maintained and the consistence of river curves' topological structure could be ensured.
In view of routine line simplification method less considering river curve's three-dimensional shape and topological structure which is applied to line simplification of river,the paper proposes a method of river line simplification considering three-dimensional shape characteristics.On the basis of three-dimensional Douglas-Peucker(3D D-P)algorithm,a three-dimensional scatter point queuing method is proposed.In this algorithm,points set in river curves are queued by river curves' three-dimensional feature,which would be divided into initial queue process,"3 in 1"combination queue process and adjusting constraint point position process.Then,some proportional points corresponding with compression ratio are deleted from queue's rear.Finally,simplified river curves are reconstructed by points' order in river curve.The results of experiment show that river curves' three-dimensional shape feature could be maintained and the consistence of river curves' topological structure could be ensured.
引文
[1]Wu Hehai.Research on Fundamental Theory and Technical Approaches of Automated Map Generalization[J].Journal of the Wuhan Technical University of Surveying and Mapping,2000,25(5):377-386(毋河海.地图信息自动综合基本问题研究[J].武汉测绘科技大学学报,2000,25(5):377-386)
[2]Zhang Qingnian.Generalization of Drainage Network with Density Differences[J].Acta Geodaetica et Cartographica Sinica,2006,35(2):191-196(张青年.顾及密度差异的河系简化[J].测绘学报,2006,35(2):191-196)
[3]Ai Tinghua,Liu Yaolin,Huang Yafeng.The Hierarchical Watershed Partitioning and Generalization of River Network[J].Acta Geodaetica et Cartographica Sinica,2007,36(2):231-236(艾廷华,刘耀林,黄亚锋.河网汇水区域的层次化剖分与地图综合[J].测绘学报,2007,36(2):231-236)
[4]Stanislawski L V.Feature Pruning by Upstream Drainage Area to Support Automated Generalization of the United States National Hydrography Dataset[J].Computers,Environment and Urban Systems,2009,33(5):325-333
[5]Deng Min,Chen Jie,Li Zhilin,et al.An Improved Local Measure Method for the Importance of Vertices in Curve Simplification[J].Geography and GeoInformation Science,2009,25(1):40-43(邓敏,陈杰,李志林,等.曲线简化中节点重要性度量方法比较及垂比弦法的改进[J].地理与地理信息科学,2009,25(1):40-43)
[6]Douglas D H,Peucker T K.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J].Cartographica:The International Journal for Geographic Information and Geovisualization,1973,10(2):112-122
[7]Saalfeld A.Topologically Consistent Line Simplification with the Douglas-Peucker Algorithm[J].Cartography and Geographic Information Science,1999,26(1):7-18
[8]Wu Hehai.Multi-way Tree Structure Based on Curve Generalization Method[J].Geomatics and Information Science of Wuhan University,2004,29(6):479-483(毋河海.基于多叉树结构的曲线综合算法[J].武汉大学学报·信息科学版,2004,29(6):479-483)
[9]Chen Yi,Peng Rencan,Zheng Yidong,et al.Line Generalization Based on Douglas Both-sides Multiway Tree[J].Acta Geodaetica et Cartographica Sinica,2010,39(3):310-315(陈轶,彭认灿,郑义东.基于Douglas双侧多叉树的曲线综合算法研究[J].测绘学报,2010,39(3):310-315)
[10]Ying Shen,Li Lin.Consistent Line Simplification Based on Constraint Points[J].Geomatics and Information Science of Wuhan University,2003,28(4):488-491(应申,李霖.基于约束点的曲线一致性化简[J].武汉大学学报·信息科学版,2003,28(4):488-491)
[11]Li Z,Openshaw S.Algorithms for Automated Line Generalization1Based on a Natural Principle of Objective Generalization[J].International Journal of Geographical Information Systems,1992,6(5):373-389
[12]Zhu Kunpeng,Wu Fang,Wang Huilian,et al.Improvement and Assessment of Li-Openshaw Algorithm[J].Acta Geodaetica et Cartographica Sinica,2007,36(4):450-456(朱鲲鹏,武芳,王辉连,等.LiOpenshaw算法的改进与评价[J].测绘学报,2007,36(4):450-456)
[13]Guo Qingsheng.A Progressive Line Simplification Algorithm[J].Journal of Wuhan Technical University of Surveying and Mapping,1998,23(1):52-56(郭庆胜.线状要素图形综合的渐进方法研究[J].武汉测绘科技大学学报,1998,23(1):52-56)
[14]Wu Fang,Deng Hongyan.Using Genetic Algorithms for Solving Problemsin Automated Line Simplification[J].Acta Geodaetica et Cartographica Sinica,2003,32(4):349-335(武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-355)
[15]Ai Tinghua,Guo Renzhong,Liu Yaolin.A Binary Tree Representation of Curve Hierarchical Structure in Depth[J].Acta Geodaetica et Cartographica Sinica,2001,30(4):343-348(艾廷华,郭仁忠,刘耀林.曲线弯曲深度层次结构的二叉树表达[J].测绘学报,2001,30(4):343-348)
[16]Wang Z,Muller J C.Line Generalization Based on Analysis of Shape Characteristics[J].Cartography and Geographic Information Systems,1998,25(1):3-15
[17]Du Shihong.Analyzing Topological Changes for Structural Shape Simplification[J].Journal of Visual Languages and Computing,2014,25(4):316-332
[18]Muller J C.Fractal and Automated Line Generalization[J].The Cartographic Journal,1987,24(1):27-34
[19]Wang Qiao.Self-similarity Analysis of Cartographic Lines and Automated Lines Generalization[J].Journal of Wuhan Technical University of Surveying and Mapping,1995,20(2):123-128(王桥.线状地图要素的自相似性分析及其自动综合[J].武汉测绘科技大学学报,1995,20(2):123-128)
[20]Wu Jitao,Wang Qiao.A Study on Automatic Cartographic Generalization Using Wavelet Analysis in GIS[J].Acta Geodaetica et Cartographica Sinica,2000,29(1):71-75(吴纪桃,王桥.小波分析在GIS线状数据图形简化中的应用研究[J].测绘学报,2000,29(1):71-75)
[21]Zhu Changqing,Wang Yuhai,Li Qingquan,et al.A Model to Compress Contour Data Based on Wavelet Analysis[J].Journal of Image and Graphics,2004,9(7):841-845(朱长青,王玉海,李清泉,等.基于小波分析的等高线数据压缩模型[J].中国图象图形学报,2004,9(7):841-845)
[22]Fei Lifan,He Jin,Ma Chenyan,et al.Three Dimensional Douglas-Peucker Algorithm and the Study of Its Application to Automated Generalization of DEM[J].Acta Geodaetica et Cartographica Sinica,2006,35(3):278-284(费立凡,何津,马晨燕,等.三维Douglas-Peucker算法及其在DEM自动综合中的应用研究[J].测绘学报,2006,35(3):278-284)
[23]He Jin,Fei Lifan,Huang Lina,et al.Study on the Method of Indirect Generalization for Contour Lines Based on the 3D Douglas-Peucker Algorithm[J].Acta Geodaetica et Cartographica Sinica,2013,42(3):467-473(何津,费立凡,黄丽娜,等.三维Douglas-Peucker算法的等高线间接综合方法研究[J].测绘学报,2013,42(3):467-473)
[24]Huang Lina.Study on the Integrated Generalization of Re1ief and Water System Based on General DEM[D].Wuhan:Wuhan University,2010(黄丽娜.基于广义DEM的地貌与水系要素一体化综合研究[D].武汉:武汉大学,2010)
[25]Deng Min,Fan Zide,Liu Huimin.Performance Evaluation of Line Simplification Algorithms Based on Hierarchical Information Content[J].Acta Geodaetica et Cartographica Sinica,2013,42(5):767-773(邓敏,樊子德,刘慧敏.层次信息量的线要素化简算法评价研究.测绘学报,2013,42(5):767-773)
[2]Zhang Qingnian.Generalization of Drainage Network with Density Differences[J].Acta Geodaetica et Cartographica Sinica,2006,35(2):191-196(张青年.顾及密度差异的河系简化[J].测绘学报,2006,35(2):191-196)
[3]Ai Tinghua,Liu Yaolin,Huang Yafeng.The Hierarchical Watershed Partitioning and Generalization of River Network[J].Acta Geodaetica et Cartographica Sinica,2007,36(2):231-236(艾廷华,刘耀林,黄亚锋.河网汇水区域的层次化剖分与地图综合[J].测绘学报,2007,36(2):231-236)
[4]Stanislawski L V.Feature Pruning by Upstream Drainage Area to Support Automated Generalization of the United States National Hydrography Dataset[J].Computers,Environment and Urban Systems,2009,33(5):325-333
[5]Deng Min,Chen Jie,Li Zhilin,et al.An Improved Local Measure Method for the Importance of Vertices in Curve Simplification[J].Geography and GeoInformation Science,2009,25(1):40-43(邓敏,陈杰,李志林,等.曲线简化中节点重要性度量方法比较及垂比弦法的改进[J].地理与地理信息科学,2009,25(1):40-43)
[6]Douglas D H,Peucker T K.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J].Cartographica:The International Journal for Geographic Information and Geovisualization,1973,10(2):112-122
[7]Saalfeld A.Topologically Consistent Line Simplification with the Douglas-Peucker Algorithm[J].Cartography and Geographic Information Science,1999,26(1):7-18
[8]Wu Hehai.Multi-way Tree Structure Based on Curve Generalization Method[J].Geomatics and Information Science of Wuhan University,2004,29(6):479-483(毋河海.基于多叉树结构的曲线综合算法[J].武汉大学学报·信息科学版,2004,29(6):479-483)
[9]Chen Yi,Peng Rencan,Zheng Yidong,et al.Line Generalization Based on Douglas Both-sides Multiway Tree[J].Acta Geodaetica et Cartographica Sinica,2010,39(3):310-315(陈轶,彭认灿,郑义东.基于Douglas双侧多叉树的曲线综合算法研究[J].测绘学报,2010,39(3):310-315)
[10]Ying Shen,Li Lin.Consistent Line Simplification Based on Constraint Points[J].Geomatics and Information Science of Wuhan University,2003,28(4):488-491(应申,李霖.基于约束点的曲线一致性化简[J].武汉大学学报·信息科学版,2003,28(4):488-491)
[11]Li Z,Openshaw S.Algorithms for Automated Line Generalization1Based on a Natural Principle of Objective Generalization[J].International Journal of Geographical Information Systems,1992,6(5):373-389
[12]Zhu Kunpeng,Wu Fang,Wang Huilian,et al.Improvement and Assessment of Li-Openshaw Algorithm[J].Acta Geodaetica et Cartographica Sinica,2007,36(4):450-456(朱鲲鹏,武芳,王辉连,等.LiOpenshaw算法的改进与评价[J].测绘学报,2007,36(4):450-456)
[13]Guo Qingsheng.A Progressive Line Simplification Algorithm[J].Journal of Wuhan Technical University of Surveying and Mapping,1998,23(1):52-56(郭庆胜.线状要素图形综合的渐进方法研究[J].武汉测绘科技大学学报,1998,23(1):52-56)
[14]Wu Fang,Deng Hongyan.Using Genetic Algorithms for Solving Problemsin Automated Line Simplification[J].Acta Geodaetica et Cartographica Sinica,2003,32(4):349-335(武芳,邓红艳.基于遗传算法的线要素自动化简模型[J].测绘学报,2003,32(4):349-355)
[15]Ai Tinghua,Guo Renzhong,Liu Yaolin.A Binary Tree Representation of Curve Hierarchical Structure in Depth[J].Acta Geodaetica et Cartographica Sinica,2001,30(4):343-348(艾廷华,郭仁忠,刘耀林.曲线弯曲深度层次结构的二叉树表达[J].测绘学报,2001,30(4):343-348)
[16]Wang Z,Muller J C.Line Generalization Based on Analysis of Shape Characteristics[J].Cartography and Geographic Information Systems,1998,25(1):3-15
[17]Du Shihong.Analyzing Topological Changes for Structural Shape Simplification[J].Journal of Visual Languages and Computing,2014,25(4):316-332
[18]Muller J C.Fractal and Automated Line Generalization[J].The Cartographic Journal,1987,24(1):27-34
[19]Wang Qiao.Self-similarity Analysis of Cartographic Lines and Automated Lines Generalization[J].Journal of Wuhan Technical University of Surveying and Mapping,1995,20(2):123-128(王桥.线状地图要素的自相似性分析及其自动综合[J].武汉测绘科技大学学报,1995,20(2):123-128)
[20]Wu Jitao,Wang Qiao.A Study on Automatic Cartographic Generalization Using Wavelet Analysis in GIS[J].Acta Geodaetica et Cartographica Sinica,2000,29(1):71-75(吴纪桃,王桥.小波分析在GIS线状数据图形简化中的应用研究[J].测绘学报,2000,29(1):71-75)
[21]Zhu Changqing,Wang Yuhai,Li Qingquan,et al.A Model to Compress Contour Data Based on Wavelet Analysis[J].Journal of Image and Graphics,2004,9(7):841-845(朱长青,王玉海,李清泉,等.基于小波分析的等高线数据压缩模型[J].中国图象图形学报,2004,9(7):841-845)
[22]Fei Lifan,He Jin,Ma Chenyan,et al.Three Dimensional Douglas-Peucker Algorithm and the Study of Its Application to Automated Generalization of DEM[J].Acta Geodaetica et Cartographica Sinica,2006,35(3):278-284(费立凡,何津,马晨燕,等.三维Douglas-Peucker算法及其在DEM自动综合中的应用研究[J].测绘学报,2006,35(3):278-284)
[23]He Jin,Fei Lifan,Huang Lina,et al.Study on the Method of Indirect Generalization for Contour Lines Based on the 3D Douglas-Peucker Algorithm[J].Acta Geodaetica et Cartographica Sinica,2013,42(3):467-473(何津,费立凡,黄丽娜,等.三维Douglas-Peucker算法的等高线间接综合方法研究[J].测绘学报,2013,42(3):467-473)
[24]Huang Lina.Study on the Integrated Generalization of Re1ief and Water System Based on General DEM[D].Wuhan:Wuhan University,2010(黄丽娜.基于广义DEM的地貌与水系要素一体化综合研究[D].武汉:武汉大学,2010)
[25]Deng Min,Fan Zide,Liu Huimin.Performance Evaluation of Line Simplification Algorithms Based on Hierarchical Information Content[J].Acta Geodaetica et Cartographica Sinica,2013,42(5):767-773(邓敏,樊子德,刘慧敏.层次信息量的线要素化简算法评价研究.测绘学报,2013,42(5):767-773)