Research And Implementation Of The Delaunay Triangulation Algorithm In The Planar Domain

The research about Digital Elevation Model(DEM) has became a classic research field of Geographic Information System(GIS). It is widely used in surveying, remote sensing,3-d terrain visualization, and so on. Triangulated Irregular Network(TIN) is the most important model of DEM. TIN is a consecutive triangular network by using the scattered points. The shape of the TIN depends on the distribution and location of scattered points.Delaunay triangulation is regarded as a regular triangulation algorithm. It can prevent the formation of long triangles as far as possible and can ensure the triangulation network is the only one. Therefore, Delaunay triangulation is regarded as the best network in TIN. It can adapt to the regular and irregular distribution of data and can hand special terrain flexibly.The thesis mainly study the construction of Delaunay triangulation on plane domain and improved the algorithm. This main content of the thesis are as follows:(1) The thesis sums up the research status of Delaunay triangulation algorithm and constrained Delaunay triangulation algorithm, especially the research status of the point location algorithm and constrained edges inserting algorithm.(2) The thesis focus on the research of incremental insertion algorithm. And the thesis improves the point location algorithm in order to solve point insertion problem of low efficiency. The algorithm regard the latest triangle which contains the point to be inserted as the primary triangle. It can reduce the number of triangles to look up and educes the time in the process of insertion point positioning, which can effectively improve the efficiency of the construction of Delaunay triangulation.(3) For lacks of the "insert-exchange" algorithm, this thesis considers the problem that the constraint edge is tangent to the triangle vertex. If two adjacent triangles are composed of convex quadrangle, the algorithm exchanges there diagonal; if two adjacent triangles are composed of concave quadrangle, the algorithm inserts the intersections on the constrained edge; if the constrained edge and the triangle vertex are intersectant, the algorithm split constrained edge to improved the algorithm.