Line Simplification of Three-dimensional Drainage Considering Topological Consistency

doi:10.11947/j.AGCS.2016.20150288

Abstract

Abstract: In view of the fact that drainage line simplification using conversional methods is usually hard to keep the three-dimensional characteristics and topological relationships, this paper proposes a new method of three-dimensional drainage line simplification which maintains topological consistency. It firstly expends the conversional D-P algorithm to three-dimensional in order to keep three-dimensional characteristics during the simplification. Then it constructs tree structures for drainage lines to express their topological relations. Finally, it simplifies river lines and reconstructs topological relations of main streams and their branches according to the hierarchical order of water system tree. The experimental results show that this method has a higher accuracy in simplification and can maintain not only three-dimensional shape characteristics of water system but also the topological consistency at river confluences.

Key words: D-P algorithm, topological relationship, three-dimensional line simplification, water system simplification

CLC Number:

P208

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.

References

[1] 王家耀,孙群,王光霞,等. 地图学原理与方法[M]. 北京:科学出版社, 2006:209-339. WANG Jiayao, SUN Qun, WANG Guangxia, et al. Principle and Method of Cartography[M]. Beijing:Science Press, 2006:209-339.
[2] 张青年. 顾及密度差异的河系简化[J]. 测绘学报, 2006, 35(2):191-196. ZHANG Qingnian. Generalization of Drainage Network with Density Differences[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2):191-196.
[3] 艾廷华,刘耀林,黄亚锋.河网汇水区域的层次化剖分与地图综合[J]. 测绘学报, 2007, 36(2):231-236, 243. 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, 243.
[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] 邓敏,陈杰,李志林,等. 曲线简化中节点重要性度量方法比较及垂比弦法的改进[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.
[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] VAN OOSTEROM P, SCHENKELAARS V. The Development of an Interactive Multi-scale GIS[J]. International Journal of Geographical Information Systems, 1995, 9(5):489-507.
[8] 毋河海. 基于多叉树结构的曲线综合算法[J]. 武汉大学学报(信息科学版), 2004, 29(6):479-483. WU Hehai. Multi-Way Tree Structure Based on Curve Generalization Method[J]. Geomatics and Information Science of Wuhan University, 2004, 29(6):479-483.
[9] 陈轶, 彭认灿, 郑义东, 等. 基于Douglas双侧多叉树的曲线综合算法研究[J]. 测绘学报, 2010, 39(3):310-315. CHEN Yi, PENG Rencan, ZHENG Yidong, et al. Line Generalization Based on Douglas Both-sides Multi-way Tree[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3):310-315.
[10] LI Zhilin, OPENSHAW S. Algorithms for Automated Line Generalization1 Based on a Natural Principle of Objective Generalization[J]. International Journal of Geographical Information Systems, 1992, 6(5):373-389.
[11] 朱鲲鹏, 武芳, 王辉连, 等. Li-Openshaw算法的改进与评价[J]. 测绘学报, 2007, 36(4):450-456. 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.
[12] 艾廷华, 郭仁忠, 刘耀林. 曲线弯曲深度层次结构的二叉树表达[J]. 测绘学报, 2001, 30(4):343-348. 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.
[13] WANG Zeshen, MüLLER J C. Line Generalization Based on Analysis of Shape Characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1):3-15.
[14] 钱海忠, 武芳, 陈波, 等. 采用斜拉式弯曲划分的曲线化简方法[J]. 测绘学报, 2007, 36(4):443-449, 456. QIAN Haizhong, WU Fang, CHEN Bo, et al. Simplifying Line with Oblique Dividing Curve Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4):443-449, 456.
[15] DU Shihong.Analyzing Topological Changes for Structural Shape Simplification[J]. Journal of Visual Languages & Computing, 2014, 25(4):316-332.
[16] MULLER J C. Fractal and Automated Line Generalization[J]. The Cartographic Journal, 1987, 24(1):27-34.
[17] 王桥. 线状地图要素的自相似性分析及其自动综合[J]. 武汉测绘科技大学学报, 1995, 20(2):123-128. WANG Qiao. Self-Similarity Analysis of Cartographic Lines and the Automated Line Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1995, 20(2):123-128.
[18] 吴纪桃, 王桥. 小波分析在GIS线状数据图形简化中的应用研究[J]. 测绘学报, 2000, 29(1):71-75. 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.
[19] 朱长青,王玉海,李清泉, 等. 基于小波分析的等高线数据压缩模型[J]. 中国图象图形学报, 2004, 9(7):841-845. 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.
[20] 何津, 费立凡, 黄丽娜, 等. 三维Douglas-Peucker算法的等高线间接综合方法研究[J]. 测绘学报, 2013, 42(3):467-473. HE Jin, FEI Lifan, HUANG Li'na, 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.
[21] 应申, 李霖. 基于约束点的曲线一致性化简[J]. 武汉大学学报(信息科学版), 2003, 28(4):488-491. YING Shen, LI lin. Consistent Line Simplification Based on Constraint Points[J]. Geomatics and Information Science of Wuhan University, 2003, 28(4):488-491.
[22] 毋河海. 河系树结构的自动建立[J]. 武汉测绘科技大学学报, 1995, 20(S):7-14. WU Hehai. Automatic Establishment of River Tree Structure[J]. Journal of the Wuhan Technical University of Surveying and Mapping, 1995, 20(S):7-14.
[23] 黄丽娜. 基于广义DEM的地貌与水系要素一体化综合研究[D]. 武汉:武汉大学, 2010:97-99. HUANG Li'na. Study on the Integrated Generalization of Relief and Water System Based on General DEM[D]. Wuhan:Wuhan University, 2010:97-99.
[24] 何津, 费立凡. 解决图形冲突的受限变形所涉及的数学原则-以道路与建筑物的关系为例[J]. 武汉大学学报(信息科学版), 2007, 32(4):326-330. HE Jin, FEI Lifan. Mathematical Methods Involved in Constrained Reshaping for Solving Graphic Conflicts between Streets and Buildings[J]. Geomatics and Information Science of Wuhan University, 2007, 32(4):326-330.
[25] 邓敏, 樊子德, 刘慧敏. 层次信息量的线要素化简算法评价研究[J]. 测绘学报, 2013, 42(5):767-773, 781. 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, 781.
[26] 武芳, 邓红艳, 钱海忠, 等. 地图自动综合质量评估模型[M]. 北京:科学出版社, 2009:95-138. WU Fang, DENG Hongyan, QIAN Haizhong, et al. Quality Assess Model of Map Automatic Generalization[M]. Beijing:Science Press, 2009:95-138.