Douglas-Peucker算法全自动化的多尺度空间相似关系方法

doi:10.12082/dqxxkx.2021.210016

地球信息科学学报 ›› 2021, Vol. 23 ›› Issue (10): 1767-1777.doi: 10.12082/dqxxkx.2021.210016

• 地球信息科学理论与方法 • 上一篇下一篇

Douglas-Peucker算法全自动化的多尺度空间相似关系方法

王荣¹^,²^,³(), 闫浩文¹^,³^,^*(), 禄小敏¹^,³

1.兰州交通大学测绘与地理信息学院,兰州 730070
2.天水师范学院资源与环境工程学院,天水 741001
3.地理国情监测技术应用国家地方联合工程研究中心,兰州 730070

收稿日期:2021-01-12 修回日期:2021-03-12 出版日期:2021-10-25 发布日期:2021-12-25
通讯作者: * 闫浩文（1969—）,甘肃民勤人,博士,“长江学者”特聘教授,主要从事地图综合及多尺度空间理论研究。E-mail: haowen2010@gmail.com
作者简介:王荣（1986— ）,女,甘肃天水人,博士生,主要从事多尺度空间相似关系研究。E-mail: freefly_99@126.com
基金资助:
国家自然科学基金项目(41930101);国家自然科学基金青年基金项目(41801395);甘肃省教育厅创新基金项目(2021A-110)

Automation of the Douglas-Peucker Algorithm based on Spatial Similarity Relations

WANG Rong¹^,²^,³(), YAN Haowen¹^,³^,^*(), LU Xiaomin¹^,³

1. Faculty of Geomatics, Lanzhou Jiaotong University, Lanzhou 730070, China
2. College of Resources and Environmental Engineering, Tianshui Normal University, Tianshui 741001, China
3. National-Local Joint Engineering Research Center of Technologies and Applications for National Geographic State Monitoring, Lanzhou 730070, China

Received:2021-01-12 Revised:2021-03-12 Online:2021-10-25 Published:2021-12-25
Supported by:
Youth Foundation of National Natural Science Foundation of China(41930101);Youth Foundation of National Natural Science Foundation of China(41801395);Innovation Foundation of Education Department of Gansu(2021A-110)

摘要/Abstract

摘要：

地图综合本质上是空间相似变换,研究Douglas-Peucker算法及其参数的设置,实质是研究算法的最佳距离阈值与尺度变化间的定量关系,但目前二者关系未知,导致参数设置及化简结果的选择主观性强。为此,提出以多尺度线要素空间相似关系为契合点,利用阈值参数寻优原理确定二者间定量关系,以实现基于DP算法线要素的全自动化简。结果表明：① 二次函数是描述最佳距离阈值与尺度变化间定量关系的最优函数;② 针对来源于相同地理特征区,如长江下游平原,的线要素可行,利用同一最佳距离阈值可实现基于DP算法线要素的全自动化简,且化简结果与已有成果数据吻合度较高;而来源于不同地理特征区域,如长江下游平原和江淮平原,的线要素,用同一最佳距离阈值化简是不合理。因此,应选择不同的最佳距离阈值,以实现不同地理特征区域线要素的DP算法全自动化简。

关键词: 地图综合, 空间相似关系, 尺度变化, 参数寻优, 几何精度, Douglas-Peucker算法, 地理特征, 最佳距离阈值

Abstract:

Map generalization is in essence a spatial similarity transformation of maps. Studying the Douglas-Peucker algorithm and its parameter setting is in essence studying the relationship between the optimal distance threshold of the algorithm and map scale change. However, the quantitative relationship between them is still unknown, which leads to strong subjectivity in parameter setting and selection of simplification results. Therefore, in order to realize the automated simplification of polyline based on DP algorithm, this paper proposes to take the spatial similarity evaluation model of multi-scale polylines as the coincidence point, and determine the quantitative relationship between them using the principle of threshold parameter optimization. The results indicate that quadratic function is the optimal function to describe the quantitative relationship between the optimal distance threshold and map scale change. It is feasible to use the same optimal distance to automatically simplify the polylines from the same geographical feature area based on the Douglas-Peucker algorithm, such as the polylines from the Lower Yangtze River plain. The simplification results match well with the existing target scale data. However, it is unreasonable to use the same optimal distance threshold to simplify the polylines from different geographical feature areas, such as polylines from the Lower Yangtze River plain and the Jianghuai plain. Therefore, different optimal distance thresholds should be selected to realize full automated simplification of DP algorithm for polylines from different geographical feature areas.

Key words: map generalization, spatial similarity relations, map scale change, parameter optimization, geometric accuracy, Douglas-Peucker algorithm, geographic feature, optimal distance threshold

王荣, 闫浩文, 禄小敏. Douglas-Peucker算法全自动化的多尺度空间相似关系方法[J]. 地球信息科学学报, 2021, 23(10): 1767-1777.DOI:10.12082/dqxxkx.2021.210016

WANG Rong, YAN Haowen, LU Xiaomin. Automation of the Douglas-Peucker Algorithm based on Spatial Similarity Relations[J]. Journal of Geo-information Science, 2021, 23(10): 1767-1777.DOI:10.12082/dqxxkx.2021.210016

图/表 15

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表1

多尺度线要素T寻优结果

山西山地	T= -0.0001C²+0.0098C-0.037 (C $∈$ (1,50])					长江下游平原	T= -0.00003C²+0.0026C-0.0008 (C $∈$ (1,50])
	C	5	10	25	50		C	2.5	5	10	25	50
	T/km	0.0095	0.0510	0.1455	0.2030		T/km	0.0056	0.0114	0.0222	0.0455	0.0542

表1

图11

图12

表2

表3

参考文献 29

[1]	Yan H W, Li J. Concepts of spatial similarity relations in multiscale map spaces[M]//Spatial Similarity Relations in Multi-scale Map Spaces. Cham: Springer International Publishing, 2014:45-80.
[2]	McMaster R B. Automated line generalization[J]. Cartographica: the International Journal for Geographic Information and Geovisualization, 1987, 24(2):74-111. doi: 10.3138/3535-7609-781G-4L20
[3]	Ai T H, Ke S, Yang M, et al. Envelope generation and simplification of polylines using Delaunay triangulation[J]. International Journal of Geographical Information Science, 2017, 31(2):297-319. doi: 10.1080/13658816.2016.1197399
[4]	Shen Y L, Ai T H, Wang L, et al. A new approach to simplifying polygonal and linear features using superpixel segmentation[J]. International Journal of Geographical Information Science, 2018, 32(10):2023-2054. doi: 10.1080/13658816.2018.1485926
[5]	Kronenfeld B J, Stanislawski L V, Buttenfield B P, et al. Simplification of polylines by segment collapse: Minimizing areal displacement while preserving area[J]. International Journal of Cartography, 2020, 6(1):22-46. doi: 10.1080/23729333.2019.1631535
[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[M]//Classics in Cartography. Chichester, UK: John Wiley & Sons, Ltd, 2011:15-28.
[7]	Li Z L, 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. doi: 10.1080/02693799208901921
[8]	钱海忠, 何海威, 王骁, 等. 采用三元弯曲组划分的线要素化简方法[J]. 武汉大学学报·信息科学版, 2017, 42(8):1096-1103.
	[ Qian H Z, He H W, Wang X A, et al. Line feature simplification method based on bend group division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8):1096-1103. ]
[9]	Ramer U. An iterative procedure for the polygonal approximation of plane curves[J]. Computer Graphics and Image Processing, 1972, 1(3):244-256. doi: 10.1016/S0146-664X(72)80017-0
[10]	Yan H W. Quantitative relations between spatial similarity degree and map scale change of individual linear objects in multi-scale map spaces[J]. Geocarto International, 2015, 30(4):472-482. doi: 10.1080/10106049.2014.902115
[11]	Yan H W, Shen Y Z, Li J. Approach to calculating spatial similarity degrees of the same river basin networks on multi-scale maps[J]. Geocarto International, 2016, 31(7):765-782. doi: 10.1080/10106049.2015.1076063
[12]	Chehreghan A, Ali Abbaspour R. An assessment of spatial similarity degree between polylines on multi-scale, multi-source maps[J]. Geocarto International, 2017, 32(5):471-487. doi: 10.1080/10106049.2016.1155659
[13]	Li Z L, Sui H G. An integrated technique for automated generalization of contour maps[J]. The Cartographic Journal, 2000, 37(1):29-37. doi: 10.1179/caj.2000.37.1.29
[14]	王家耀, 何宗宜, 蒲英霞. 地图学[M]. 北京: 测绘出版社, 2016.
	[ Wang J Y, He Z Y, Pu Y X. Cartography[M]. Beijing: Sino Maps Press, 2016. ]
[15]	Chehreghan A, Ali Abbaspour R. An assessment of the efficiency of spatial distances in linear object matching on multi-scale, multi-source maps[J]. International Journal of Image and Data Fusion, 2018, 9(2):95-114. doi: 10.1080/19479832.2017.1369175
[16]	何海威, 钱海忠, 段佩祥, 等. 线要素化简及参数自动设置的案例推理方法[J]. 武汉大学学报·信息科学版, 2020, 45(3):344-352.
	[ He H W, Qian H Z, Duan P X, et al. Automatic line simplification algorithm selecting and parameter setting based on case-based reasoning[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3):344-352. ]
[17]	McMaster R B. A statistical analysis of mathematical measures for linear simplification[J]. The American Cartographer, 1986, 13(2):103-116. doi: 10.1559/152304086783900059
[18]	Anderson D L, Ames D P, Yang P. Quantitative methods for comparing different polyline stream network models[J]. Journal of Geographic Information System, 2014, 6(2):88-98. doi: 10.4236/jgis.2014.62010
[19]	Fan H C, Zipf A, Fu Q, et al. Quality assessment for building footprints data on OpenStreetMap[J]. International Journal of Geographical Information Science, 2014, 28(4):700-719. doi: 10.1080/13658816.2013.867495
[20]	Fan H C, Yang B S, Zipf A, et al. A polygon-based approach for matching OpenStreetMap road networks with regional transit authority data[J]. International Journal of Geographical Information Science, 2016, 30(4):748-764. doi: 10.1080/13658816.2015.1100732
[21]	Li B N, Fonseca F. TDD: A comprehensive model for qualitative spatial similarity assessment[J]. Spatial Cognition & Computation, 2006, 6(1):31-62.
[22]	Zhang M. Methods and implementations of road-network matching[EB/OL]. 2009.
[23]	武芳, 朱鲲鹏. 线要素化简算法几何精度评估[J]. 武汉大学学报·信息科学版, 2008, 33(6):600-603.
	[ Wu F, Zhu K P. Geometric accuracy assessment of linear features' simplification algorithms[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6):600-603. ]
[24]	顾腾, 陈晓勇, 刘成强. 一种Douglas-Peucker与Li-Openshaw结合改进的曲线化简方法[J]. 东华理工大学学报(自然科学版), 2016, 39(4):396-400.
	[ Gu T, Chen X Y, Liu C Q. 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. ]
[25]	陈竞男, 钱海忠, 王骁, 等. 提高线要素匹配率的动态化简方法[J]. 测绘学报, 2016, 45(4):486-493.
	[ Chen J N, Qian H Z, Wang X A, et al. Improving the matching rate of line feature by using dynamic simplification[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4):486-493. ]
[26]	郭仁忠. 空间分析(2版)[M]. 北京: 高等教育出版社, 2001.
	[ Guo R Z. Spacial analysis[M]. Beijing: Higher Education Press, 2001. ]
[27]	White E R. Assessment of line-generalization algorithms using characteristic points[J]. The American Cartographer, 1985, 12(1):17-28. doi: 10.1559/152304085783914703
[28]	李成名, 郭沛沛, 殷勇, 等. 一种顾及空间关系约束的线化简算法[J]. 测绘学报, 2017, 46(4):498-506.
	[ Li C M, Guo P P, Yin Y, et al. A line simplification algorithm considering spatial relations between two lines[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4):498-506. ]
[29]	Joao E M. Causes and consequences of map generalization[M]. London: Taylor and Francis, 1998.

几何指标	原比例尺数据（L_M₁）			成果参照数据（L_M₂）			本文的化简结果（L）
几何指标	边界线	道路	河流	边界线	道路	河流	边界线	道路	河流
长度/km	198.9993	27.0565	153.7918	165.6861	26.1494	152.7020	165.6059	26.2379	148.6358
弯曲度	1.4493	1.5547	25.5883	1.1969	1.5103	25.0681	1.2067	1.5121	25.5663

线要素	成果参照数据				本文算法化简结果
线要素	LR	SR	PE/km	SMD	LR′	SR′	PE′/km	SMD′
边界	0.8326	0.8258	0.2063	0.8070	0.8322	0.8324	0.1306	0.0998
道路	0.9665	0.9714	0.0054	0.3323	0.9697	0.9725	0.0114	0.4565
河流	0.9929	0.9796	0.0058	0.6046	0.9664	0.9991	0.0169	0.1203

Douglas-Peucker算法全自动化的多尺度空间相似关系方法

Automation of the Douglas-Peucker Algorithm based on Spatial Similarity Relations

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 29

相关文章 7

Metrics

本文评价

推荐阅读 0

[1]	金澄, 安晓亚, 崔海福, 赵宇君, 王惠. 矢量瓦片地图线化简算法研究[J]. 地球信息科学学报, 2019, 21(10): 1502-1509.
[2]	徐智邦, 王中辉, 闫浩文, 武芳, 段晓旗, 孙立. 结合POI数据的道路自动选取方法[J]. 地球信息科学学报, 2018, 20(2): 159-166.
[3]	杜世宏, 雒立群, 赵文智, 郭舟. 多尺度空间关系研究进展[J]. 地球信息科学学报, 2015, 17(2): 135-146.
[4]	张栋海, 黄丽娜, 刘晖, 唐健. 基于MapReduce的多机并行DP算法与实验分析[J]. 地球信息科学学报, 2013, 15(1): 55-60.
[5]	李爱勤, 李德仁, 龚健雅, 邓轶. GIS的空间数据多比例尺表达与处理概念框架[J]. 地球信息科学学报, 2009, 11(5): 645-651.
[6]	许珺. 对于线状地理特征空间关系的自然语言理解[J]. 地球信息科学学报, 2008, 10(3): 363-369.
[7]	王美珍, 沈婕, 苏昆. 移动环境中居民地综合算法的应用[J]. 地球信息科学学报, 2008, 10(2): 171-176.