高效构建Delaunay三角网数字地形模型算法研究

北京大学学报（自然科学版）

高效构建Delaunay三角网数字地形模型算法研究

胡金星, 潘懋, 马照亭, 吴焕萍

北京大学地球与空间科学学院，北京，100871

收稿日期:2002-10-09 出版日期:2003-09-20 发布日期:2003-09-20

Study on Faster Algorithm for Constructing Delaunay Triangulations DTM

HU Jinxing, PAN Mao, MA Zhaoting, WU Huanping

School of Earth and Space Sciences, Peking University, Beijing, 100871

Received:2002-10-09 Online:2003-09-20 Published:2003-09-20

摘要/Abstract

摘要： 在对传统构建Delaunay三角剖分(尤其是分割－合并)算法进行分析的基础上，采用自适应格网划分方法对点集进行排序、分割，并按照逆序合并Delaunay子三角网，然后进行约束处理，快速、高效地实现了Delaunay三角网的构建；对Delaunay子三角网合并、地性线处理、平三角形处理等关键问题进行了描述。实测结果表明，该算法的时间复杂度接近于O(n）。

关键词: Delaunay三角网, 约束Delaunay三角网, 数字地形模型

Abstract: Based on the analysis of common Delaunay triangulations methods, especially the divide-and-conquer method, a faster algorithm for constructing Delaunay triangulations is presented. It divides the point set by self-adaptive grid, constructs and merges the sub-triangulations. The key problems of merging sub-triangulations, dealing with the terrain features and the flat triangles are described. The experiments show that the expected time of the algorithm is O(n).

Key words: DTM, Delaunay triangulations, constrained Delaunay triangulations

中图分类号:

TP391

胡金星, 潘懋, 马照亭, 吴焕萍. 高效构建Delaunay三角网数字地形模型算法研究[J]. 北京大学学报（自然科学版）.

HU Jinxing,PAN Mao,MA Zhaoting,WU Huanping. Study on Faster Algorithm for Constructing Delaunay Triangulations DTM[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2003/V39/I5/736

[1]	朱强,孙敏,陈秀万. 基于动态数字地形模型的流域产汇流模拟方法[J]. 北京大学学报（自然科学版）, 2009, 45(5): 805-810.
[2]	许丽敏,薛安,. 基于Delaunay三角网与Voronoi图联合提取等高线骨架的地形重建算法研究[J]. 北京大学学报（自然科学版）, 2009, 45(4): 647-652.