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.