Research On Triangulation Algorithm

Triangulation is one of the important research contents in computer aided geometry design, geometry modeling 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 are: 2D triangulation algorithms, 3D triangulation algorithms and triangulation algorithms with charactersitic constraints.For 2D triangulation algorithms, we first introduce the definition of 2D triangulation. Then we introduce some classic algorithms at this area, and analysis these algorithms. Based on all these algorithms, we will introduce two new algorithms in detail: triangulation algorithm based on layered convex hall, triangulation algorithm based on graph. These two algorithms give out new methods to resolve the problem of triangulation.For 3D triangulation algorithms, we first introduce the definition of 3D triangulation. Then we introduce a traditional algorithm, which is based on convex hall. But this algorithm has some limits. So we introduce a new algorithm, which will resolve the problem of 3D triangulation very well.For triangulation algorithms with charactersitic constraints, we will discuss a algorithm for overall Delaunay triangulation of 2D scattered data with charactersitic constraints. The outer polygonal boundary and inner polygonal holes that scattered data may have and the characteristic constraints which could be ploygons and ploylines could be stored in a generic data structure. The overall Delaunay triangulation propertie could be satisfied by inserting a few of points using a technique called"half-scparated additional characteristic point inserting".