Research On Constrained Delaunay Triangulation And Some Other Related Algorithm

The mesh generation has the widespread application in the fields of the finite element analysis, computer graphics, science computation visual, biomedicine and geographic information system and so on. It is the key factor to effect the development of these areas, so there are many scholars research it recently.In multitudinous mesh generation algorithm, as Delaunay triangle method is very efficient, the quality of the produced mesh is good, perfect mathematics rationale and its judgment criterion, it suits the two-dimensional surface and the three- dimensional entity which will be divided into mesh, and has incomparable superiorly place than other algorithms. Some aspects have been researched in the paper as follows:1) The constrained Delaunay triangle algorithm has been researched thoroughly based on calculates geometry theory. The stochastic perturbation algorithm has been introduced into the algorithms of point by point insertion and it is effective to avoided degenerated phenomenon and five points of altogether the balls, also it can avoid the multi-spots coplane causing the position error.2) Two crucial questions have been discussed emphatically in this paper: How to solve the boundary and the bounding surface uniform question in the assigned region and how to solve the sliver problem. Based on analyzing the mutual geometries positions which has relations with the three-dimensional space center point,edges and surfaces, a suitable restoring algorithm and the sliver elimination algorithm which are suit to all kinds of complex situation boundary is proposed. The key question which is influence the mesh quality has been solved by using them.3) Based on boundary restoring and sliver elimination, the mesh quality can be ensured by using the technology of local transform in contiguous segements and meshing slippery.The Delaunay triangle algorithm, Boundary restoring algorithm and Sliver elimination algorithm are indicated to be efficient, general, high quality and easy to be realized in experiments.