为了研究数字地表模型的快速生成方法，在总结传统Delaunay三角化算法的基础上，给出了一个基于四叉树结构的数字地表模型快速生成算法的详细设计，该算法的基本思想是首先利用四叉树结构来对离散点进行分割，然后对四叉树叶节点进行Delaunay三角化，再两两合并四叉树节点三角网的凸壳，以快速生成地表表格网模型，该算法是以四叉树为基本单位为实现限定边和限定多边形的快速嵌入，最后给出了算法在不同情况下的测试结果，并对测试结果进行了具体分析，给出了算法的时间效率分析和空间复杂性分析，实测数据结果表明，该算法有着较好的性能，而且也非常稳定，通过实测结果分析和算法的时间效率分析，可以得到算法的时间效率近似为O(nlog(n）），通过算法的空间复杂性分析可以看出，算法可以自动适应不同的点空间分布情况，而且采用四叉树结构也非常有利于限定边和限定多边形的嵌入。

In this paper, an algorithm to generate digital terrain model rapidly is presented. The algorithm is based on the constrained delaunay triangulation(CDT) algorithm. The algorithm achieves a high performance by efficient managing data for the digital terrain model by quad tree, and by reducing the calculation of the algorithm by quad tree. At first, the discrete points of the digital terrain model are distributed to different leaf nodes of the quad tree; then, the points in the leaf node of quad tree are triangulated by delaunay triangulation algorithm; at Last, meshes in the nodes which are neighborhood in space are coalesced together to generate a new smooth mesh. The algorithm is high performance because in the coalition which only need to deal with the points in the hull of the mesh in each node of quad tree. Moreover, the constrained edges and constrained polygons can be integrated to the mesh quickly by using quad tree structure. In the paper, the test results of the algorithm and the analysis to the test results are also presented. Moreover, a test picture of the algorithm is illustrated. In the last part of the paper, the time cost analysis of the algorithm and the spatial characteristics analysis of the algorithm are presented. The test results show that the algorithm not only has excellent performance but also is robust. The time cost analysis of the algorithm shows that the expected time of the algorithm is O(n log( n )), and the analysis of the spatial characteristics of the algorithm shows that algorithm can be adaptive to different spatial distributed situation of the points set to be triangulated. Meanwhile, the constrained edges and the constrained polygons can be integrated into the triangulated mesh efficiently with the help of quad tree structure of the algorithm.