Research On Triangulation Algorithm

Triangulation is one of the important research contents in computer aided geometry design, geometry modelling and computer graphics. For the triangulation algorithm design, the most important is to make the algorithm have low time complexity and to create net lattice with high quality. Triangulation algorithm has significant applications in computational geometry, curved surface construction and finite element grid generation. Research contents of this paper is as follows:First, some fundamental theories of discrete point and polygon triangulation are introduced, and related definitions such as Voronoi graph and Delaunay triangulation are described, including the optimization rule.Secondly, the polygon triangulation has been studied. It has introduced the definitions related to convex polygon and the convex partition algorithm first. In convex partition, the peculiar case is that the generated convex polygon is a triangle. The main idea of the algorithm is to delete the branch point first (meanwhile it is a convex point) by cutting the ears to make the two chain used to the partition be monotonous, then to partition the two chains. Unfortunately there will be the long and narrow triangles created in the partition with this algorithm. So when a triangle is produced, the Delaunay triangulation optimization criterion is used in order to generate triangles with much better quality.The main body of this paper is described in the fourth chapter. Some triangulation algorithms for a scattered point set in the plane are introduced and analysed by comparision after the definition of triangulation for a scattered point set in the plane. Then, a new triangulation algorithm for a scattered point set in the plane is proposed under Delaunay triangulation optimization criterion. The main idea of the algorithm is that a triangle satisfying the conditions of the triangulation is generated first, then the points satisfying the conditions of the triangulation are to be searched to the outside of the triangle to create new triangles, this process is repeated until all given points are dealt with. The time complexity of this algorithm is O ( n log n ). The ill triangles are avoided being created and the quality of net partition is improved greatly and the partition is suitable to the grid generation for finite element analysis.Last, the triangulation algorithms in the plane are generalized to the three dimensional space. The related concepts and some important algorithms for convex hull of point set in the plane are introduced first. Then two partition algorithms for point set in the tree dimension are given. The idea of one of them is that the convex hull is computed first, then the points satisfying the condition of partition are selected by the value of a determinant of four order to partition the point set. The time complexity of this algorithm is O ( n log n ). And the idea of the other algorithm is that the convex hull is computed for the given point set, then the convex hull for the rest points. Repeat this until there are less than three points left. The key step is the link between any adjacent two convex hulls. The partition with high quality can be generated with this algorithm.