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

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

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