结合质心Voronoi图优化的三维Douglas-Peucker地形简化算法

在多尺度TIN的自动构建过程中,为使各尺度数据保持地形的主要特征,需要选择合适的地形简化方法提取地形的结构特征信息。传统的3D Douglas-Peucker算法通过设定距离阈值参数对地形进行简化,简化后只保留了山脊线、山谷线等主要地形特征,而未考虑局部细节,难以顾及局部地形起伏变化明显的区域;而质心Voronoi图能够以地形因子作为密度函数,通过迭代驱动种子点向地形起伏较大的区域聚集,但其在主要地形特征的表达方面有缺失。为此,本文将二者的特点结合,在利用传统的3D Douglas-Peucker算法简化的同时,通过质心Voronoi图迭代加入局部起伏较大的特征点,综合考虑主要结构特征及局部起伏对地形进行简化,并在多个简化级别下对原始3D Douglas-Peucker算法和本文优化算法进行了对比。实验结果表明,相对于原始算法,本文优化算法在各简化级别下简化误差降低13.6%以上,具有更高的地形表达精度,且能够更好地逼近原始地形。

A 3D Douglas-Peucker Terrain Simplification Algorithm Optimized Using Centroidal Voronoi Diagram

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.