Journal of Geo-information Science >
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)
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.
ZHANG Na , WANG Lei , YIN Nan . A 3D Douglas-Peucker Terrain Simplification Algorithm Optimized Using Centroidal Voronoi Diagram[J]. Journal of Geo-information Science, 2022 , 24(7) : 1245 -1253 . DOI: 10.12082/dqxxkx.2020.210812
表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.
|
/
〈 |
|
〉 |