Research On Delaunay Triangulation Algorithm Based On Flip

Triangulation is an important research in computational geometry,CAD,computer graphics and surface reconstruction. Based on the extremely broad application of triangulation, this paper selects the triangulation algorithm to research.The intention is to design a simple and efficient triangulation algorithm, and apply in the areas of computer graphics.Therefore,this study is not only in the significance of theoretical, but also great in the value of practical.This paper study the triangulation for a scattered point set in the plane. According to study the classical algorithm, there are shortcomings of common Delaunay triangulation algorithm on the arbitrary polygon, such as low efficiency and the wrong result of the irregular position, when it chooses the candidate vertex. To solve this problem, this paper propose a new Delaunay triangulation algorithm. Through improving the Graham scan method, it is not only calculate the convex hull, but also generate the initial triangulation. Then, using the Delaunay flip method transforms the initial triangulation into the optimal Delaunay triangulation.This algorithm can avoid generating the pathological triangulation and improve the performance of conventional algorithm. This algorithm is simple and universal. To verify the algorithm, this paper designs an algorithm using C language. It was compared with the classical algorithm. The results show that this algorithm is right, effective and optimal performance.It can avoid the pathological triangles and get the optimal Delaunay triangulation.