The Three Dimensional Douglas-Peucker Algorithm for Generalization between River Network Line Element and DEM

doi:10.11947/j.AGCS.2016.20140584

Abstract

Abstract: At present, the three dimensional Douglas-Peucker (3D_DP) algorithm is mainly used on generalization of a single type of DEM. This paper introduces the "bending adjustment index" to improve the 3D_DP algorithm, and puts forward a new method for generalizing river network and DEM in three-dimensional space. In this method, river network line vector data are extracted into 3D discrete point data sets which are added elevation attributes, and then they are merged with the 3D discrete point data sets of DEM. The generalization operations are made by the improved 3D_DP algorithm after the hierarchical selection of river networks. Through the contrast and analysis of the experimental results, the well experiment results have been achieved. Under the role of bending adjustment index, the overall distribution form of the rivers and the main terrain features can be reserved reasonably on the generalization. The river network and DEM data were generalized under the same simplified factor in this method. It improves the quality of the cartography generalization.

Key words: bending adjustment Index, 3D Douglas-Peucker algorithm, cartography generalization

CLC Number:

P208

DOU Shiqing, ZHAO Xuesheng, LIU Chengjun, LIN Yawen, ZHAO Yanqin. 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.

References

[1] 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]. The Canadian Cartographer, 1973, 10(2):112-122.
[2] 杨得志, 王杰臣, 闾国年. 矢量数据压缩的Douglas-Peucker算法的实现与改进[J]. 测绘通报, 2002(7):18-22. YANG Dezhi, WANG Jiechen, LV Guonian. Study of Realization Method and Improvement of Douglas-Peucher Algorithm of Vector Data Compressing[J]. Bulletin of Surveying and Mapping, 2002(7):18-22.
[3] 费立凡,何津,马晨燕,等. 3维Douglas-Peucker算法及其在DEM自动综合中的应用研究[J]. 测绘学报, 2006, 35(3):278-284. 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.
[4] LI Yang, HU Peng, FAN Qingsong, et al. The Generalization Based on 3 Dimensional Douglas-Peucker Algorithm in New DEM Model[C]//Proceedings of International Workshop on Education Technology and Training and International Workshop on Geoscience and Remote Sensing. Shanghai:IEEE, 2008:283-286.
[5] FEI Lifan, HE Jin. A Three-dimensional Douglas-Peucker Algorithm and Its Application to Automated Generalization of DEMs[J]. International Journal of Geographical Information Science, 2009, 23(6):703-718.
[6] 何津, 费立凡. 再论三维Douglas-Peucker算法及其在DEM综合中的应用[J]. 武汉大学学报(信息科学版), 2008, 33(2):160-163. HE Jin, FEI Lifan. Further Study on Three Dimensional Douglas-Peucker Algorithm and Its Application to Generalization of DEM[J]. Geomatics and Information Science of Wuhan University, 2008, 33(2):160-163.
[7] 刘敏. 基于三维道格拉斯改进算法的地貌自动综合研究--以在黄土高原的实验为例[D]. 西安:西北大学, 2007. LIU Min. Relief Automated Generalization Based on the Improved Three Dimensional Douglas-Peucker Algorithm:A Case Study in the Loess Plateau[D]. Xi'an:Northwest University, 2007.
[8] 黄丽娜,费立凡. 采用3D D-P算法的等高线三维综合实验研究[J]. 武汉大学学报(信息科学版), 2010, 35(1):55-58. HUANG Lina, FEI Lifan. Experimental Investigation on the Three Dimension Generalization of Contour Lines Using 3D D-P Algorithm[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1):55-58.
[9] 何津,费立凡, 黄丽娜, 等. 三维Douglas-Peucker算法的等高线间接综合方法研究[J]. 测绘学报, 2013, 42(3):467-473. 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.
[10] 朱雪坚, 叶远智, 汤国安. 运用三维Douglas-Peucker算法提取DEM地形特征[J]. 测绘通报, 2014(3):118-121. DOI:10.13474/j.cnki.11-2246.2014.0105. ZHU Xuejian, YE Yuanzhi, TANG Guoan. Three Dimensional Douglas-Peucker Algorithm Based Extraction of Topographical Features from DEM[J]. Bulletin of Surveying and Mapping, 2014(3):118-121. DOI:10.13474/j.cnki.11-2246.2014.0105.
[11] 张俊峰, 费立凡, 黄丽娜, 等. 利用3D_DP和Quad_TIN的地形实时动态显示算法研究[J]. 武汉大学学报(信息科学版), 2011, 36(3):346-350. ZHANG Junfeng, FEI Lifan, HUANG Lina, et al. Real-Time Dynamic Rendering Algorithm of Terrain Using 3D_DP Method and Quad_TIN Model[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3):346-350.
[12] 窦世卿, 刘成军, 林亚文, 等. 基于改进的三维Douglas-Peucker算法的多波束测深数据抽稀方法[J]. 科技导报, 2014, 32(19):21-25. DOU Shiqing,LIU Chengjun,LIN Yawen,et al. A Method of Multi-beam Echo Sounding System Data Thinning Based on Improved 3D Douglas-Peucker Algorithm[J]. Science & Technology Review, 2014, 32(19):21-25.
[13] 舒方国. 基于多Agent的等高线与河流协同综合方法研究[D]. 南京:南京师范大学, 2012. SHU Fangguo. Collaborative Map Generalization Method of Contours and Rivers Based on Multi-agent[D]. Nanjing:Nanjing Normal University, 2012.
[14] YANG Ling, ZHANG Liqiang, KANG Zhizhong, et al. An Efficient Rendering Method for Large Vector Data on Large Terrain Models[J]. Science in China Information Sciences, 2010, 53(6):1122-1129.
[15] 李雯静, 邱佳, 林志勇, 等. 曲线弯曲识别与等高线簇结构化方法[J]. 测绘学报, 2013, 42(2):295-303. LI Wenjing,QIU Jia,LIN Zhiyong,et al. Approach of Curve Bends Recognition and Contour Cluster Structuralization[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2):295-303.
[16] 沈志峰. 电子海图岛屿多边形简化与合并算法研究[D]. 哈尔滨:哈尔滨工程大学, 2009. SHEN Zhifeng.Research on Simplification and Aggregation Algorithm of Island Polygon in Electronic Chart[D]. Harbin:Harbin Engineering University, 2009.
[17] 中国科学院地理研究所. 中国1:1000000地貌图制图规范[S]. 北京:科学出版社, 1987. Institute of Geography Research of CAS. 1:1000000 Geomorphologic Map Drawing Specification of China[S]. Beijing:Science Press, 1987.
[18] 张青年. 顾及密度差异的河系简化[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.
[19] 杨敏, 艾廷华, 刘鹏程, 等. 等高线与水网数据集成中的匹配及一致性改正[J]. 测绘学报, 2012, 41(1):152-158. YANG Min, AI Tinghua, LIU Pengcheng, et al. The Matching and Consistency Correcting in the Integration of Contour and River Network[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1):152-158.
[20] 龙毅, 曹阳, 沈婕, 等. 基于约束D-TIN的等高线簇与河网协同综合方法[J]. 测绘学报, 2011, 40(3):379-385. LONG Yi, CAO Yang, SHEN Jie, et al. Cooperative Generalization Method of Contour Cluster and River Network Based on Constrained D-TIN[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(3):379-385.