结合质心Voronoi图优化的三维Douglas-Peucker地形简化算法
张 娜(1997— ),女,山东日照人,研究生,主要从事GIS算法研究。E-mail: 1938733754@qq.com |
收稿日期: 2021-12-16
修回日期: 2022-02-22
网络出版日期: 2022-09-25
基金资助
国家自然科学基金项目(41801318)
河南省科技攻关项目(212102310432)
河南理工大学青年骨干教师资助计划项目(2019XQG-03)
河南理工大学博士基金项目(B2017-14)
A 3D Douglas-Peucker Terrain Simplification Algorithm Optimized Using Centroidal Voronoi Diagram
Received date: 2021-12-16
Revised date: 2022-02-22
Online published: 2022-09-25
Supported by
National Natural Science Foundation of China(41801318)
Key Research and Development Program of Henan Province(212102310432)
Young Backbone Teachers Funding Scheme of Henan Polytechnic University(2019XQG-03)
Doctoral Foundation of Henan Polytechnic University(B2017-14)
在多尺度TIN的自动构建过程中,为使各尺度数据保持地形的主要特征,需要选择合适的地形简化方法提取地形的结构特征信息。传统的3D Douglas-Peucker算法通过设定距离阈值参数对地形进行简化,简化后只保留了山脊线、山谷线等主要地形特征,而未考虑局部细节,难以顾及局部地形起伏变化明显的区域;而质心Voronoi图能够以地形因子作为密度函数,通过迭代驱动种子点向地形起伏较大的区域聚集,但其在主要地形特征的表达方面有缺失。为此,本文将二者的特点结合,在利用传统的3D Douglas-Peucker算法简化的同时,通过质心Voronoi图迭代加入局部起伏较大的特征点,综合考虑主要结构特征及局部起伏对地形进行简化,并在多个简化级别下对原始3D Douglas-Peucker算法和本文优化算法进行了对比。实验结果表明,相对于原始算法,本文优化算法在各简化级别下简化误差降低13.6%以上,具有更高的地形表达精度,且能够更好地逼近原始地形。
张娜 , 王磊 , 殷楠 . 结合质心Voronoi图优化的三维Douglas-Peucker地形简化算法[J]. 地球信息科学学报, 2022 , 24(7) : 1245 -1253 . DOI: 10.12082/dqxxkx.2020.210812
The purpose of terrain simplification is to use the least effective terrain information to express multi-scale terrain, in order to solve the contradiction between massive terrain data and computer hardware and meet the needs of multi-scale terrain applications. Most of the existing terrain simplification algorithms can hardly take into account both the local detailed features and overall features of the terrain. In order to keep the main features of the terrain at different scales, it is necessary to select a suitable terrain simplification method to extract the structural feature information of the terrain. The traditional 3D Douglas-Peucker algorithm, which is a commonly used algorithm, simplifies terrain by setting distance threshold parameters. However, only main terrain features such as ridgelines and valley lines are retained, areas with obvious local terrain undulations have not been taken into consideration in the simplified terrain. The Centroidal Voronoi diagram, which is an important data structure, can use the terrain factor as the density function and drive the seed points to the areas with large terrain undulations through iteration, but it has deficiencies in the representation of major topographic features. To address these deficiencies, an optimized algorithm that combines the advantages of 3D Douglas-Peucker algorithm and centroidal Voronoi diagram is proposed in this paper. Firstly, overall terrain feature points, which form the main frame of the terrain, are extracted at different scale by changing the distance threshold parameters of traditional 3D Douglas-Peucker algorithm. Then, points with large local undulations that reflects local topographic undulations are acquired by setting terrain undulations as density function while generating centroidal Voronoi diagram using Lloyd’s algorithm. Also, different amount of seed points are set to satisfy the demand of different simplification level. Meanwhile, the proportion of the two types of feature points can be modified to fulfill different level of attention to the overall and local terrain information. Combining the overall terrain feature points obtained by the traditional 3D Douglas-Peucker algorithm with the points with large local undulations obtained by centroidal Voronoi diagram, the proposed algorithm simplifies terrain by considering both the main structural features and local undulations. Finally, comparison analysis is designed and conducted at different simplification levels. Results show that, compared with the traditional 3D Douglas-Peucker algorithm, the proposed algorithm that is optimized using centroidal Voronoi diagram approximates the original terrain better and has a higher accuracy of terrain representation. The optimized algorithm reduces the simplification error by more than 13.6% at each simplification level.
表1 本文优化算法与3D Douglas-Peucker算法高程中误差对比Tab. 1 Comparison of the optimization algorithm with the 3D Douglas-Peucker algorithm for elevation mid-error |
点数/个 | |||||||||
---|---|---|---|---|---|---|---|---|---|
300 | 600 | 900 | 1200 | 1500 | 1800 | 2100 | 2400 | ||
高程中误差/m | 本文优化算法 | 23.95 | 20.91 | 17.73 | 17.19 | 14.98 | 14.57 | 13.80 | 13.08 |
3D-DP算法 | 27.71 | 25.12 | 22.36 | 21.82 | 19.57 | 18.12 | 16.82 | 16.18 | |
误差降低/% | 13.60 | 16.80 | 20.70 | 21.20 | 23.50 | 19.60 | 18.00 | 19.20 |
[1] |
|
[2] |
徐勇, 马燕, 康建成. 基于轮廓草图的三维地形建模方法研究[J]. 计算机应用与软件, 2016, 33(3):126-128.
[
|
[3] |
张倩宁. 基于地形复杂度的LiDAR点云简化方法研究[D]. 成都: 西南交通大学, 2016.
[
|
[4] |
丁少鹏, 刘如飞, 蔡永宁, 等. 一种顾及地形的点云自适应坡度滤波方法[J]. 遥感信息, 2019, 34(4):108-113.
[
|
[5] |
高远. 基于Douglas-Peucker算法的等高线自动综合研究[D]. 福州: 福州大学, 2011.
[
|
[6] |
何津, 费立凡, 黄丽娜, 等. 三维Douglas-Peucker算法的等高线间接综合方法研究[J]. 测绘学报, 2013, 42(3):467-473.
[
|
[7] |
|
[8] |
李磊, 李正品, 李曦凌. 宗地界址点自动化提取算法研究[J]. 测绘地理信息, 2018, 43(2):90-92, 96.
[
|
[9] |
窦世卿, 赵学胜, 刘成军, 等. 河网线要素与DEM综合的三维Douglas-Peucker算法[J]. 测绘学报, 2016, 45(4):450-457.
[
|
[10] |
于靖, 陈刚, 张笑, 等. 面向自然岸线抽稀的改进道格拉斯—普克算法[J]. 测绘科学, 2015, 40(4):23-27.
[
|
[11] |
费立凡, 何津, 马晨燕, 等. 3维Douglas-Peucker算法及其在DEM自动综合中的应用研究[J]. 测绘学报, 2006, 35(3):278-284.
[
|
[12] |
何津, 费立凡. 再论三维Douglas-Peucker算法及其在DEM综合中的应用[J]. 武汉大学学报·信息科学版, 2008, 33(2):160-163.
[
|
[13] |
黄丽娜, 费立凡. 采用3D D-P算法的等高线三维综合实验研究[J]. 武汉大学学报·信息科学版, 2010, 35(1):55-58.
[
|
[14] |
张俊峰, 费立凡, 黄丽娜, 等. 利用3D_DP和Quad_TIN的地形实时动态显示算法研究[J]. 武汉大学学报·信息科学版, 2011, 36(3):346-350.
[
|
[15] |
王维. 基于Douglas-Peucker的全局性地形综合简化算法研究[D]. 武汉: 湖北大学, 2014.
[
|
[16] |
朱雪坚, 叶远智, 汤国安. 运用三维Douglas-Peucker算法提取DEM地形特征[J]. 测绘通报, 2014(3):118-121.
[
|
[17] |
郑先伟. 顾及地形特征的全球多尺度TIN自动构建及快速可视化[D]. 武汉: 武汉大学, 2015.
[
|
[18] |
|
[19] |
陈桂珍, 季鹏磊, 龚声蓉. 基于质心化的Voronoi划分图像分割算法在交通视频中的车辆检测研究[J]. 机械设计与制造, 2016(9):269-272.
[
|
[20] |
|
[21] |
|
[22] |
宋占杰, 张美, 何改云, 等. 基于质心Voronoi结构的自由曲面布点策略[J]. 吉林大学学报(工学版), 2013, 43(1):34-38.
[
|
[23] |
冀翠莲, 周慎杰, 田蕴, 等. 基于质心Voronoi结构的布点算法及应用[J]. 机械工程学报, 2008(1):168-172.
[
|
[24] |
刘盛恩, 陈向宁, 王得成. 基于质心Voronoi图重构的UDSM边折叠简化[J]. 应用光学, 2020, 41(1):127-133.
[
|
[25] |
郎玲玲, 程维明, 朱启疆, 等. 多尺度DEM提取地势起伏度的对比分析——以福建低山丘陵区为例[J]. 地球信息科学, 2007, 9(6):1-6.
[
|
[26] |
中科图新_全国5米地形OEM[EB/OL]. 2022. http://www.tuxingis.com/resource/dem_5_down-load.html.
|
/
〈 |
|
〉 |