Delaunay Triangulation Generation Algorithm And Its Applied Research

Triangulation is widely used in geology, computational geometry, graphics, images, and many other science and biomedical and other fields. Model can be quickly built by triangulation techniques.It has a good performance in practical engineering. In particular, constrained Delaunay triangulation is considered the optimal triangulation of data modeling. It is the original, more accurately reflect the true and objective information. It with the other algorithm is superior than the other algorithms.Therefore, many scholars have been studying the hot spots.Given the current constrained Delaunay triangulation construction algorithm for the concave polygon in the influence domain case, the algorithm is not very stable, or even failure, of the constrained Delaunay Triangulation algorithm is of great significance and value. This specific study as follows:1. The knowledge of-mesh generation technology,Conyex Hull, Voronoi diagram, constrained Delaunay triangulation of non-construction algorithm and the constrained Delaunay Triangulation Algorithm has been researehed. Constrained Delaunay Triangulation Algorithm defects have been presented. A diagonal exchange based on the improved algorithm is given. It can effectively shorten the time to construct the triangulation when we use the incremental insertion algorithm to construct triangulation with STL.2. Research the constraints of the embedding process. Provide the interface to achieve the dynamic insertion constraints.3.This algorithm introduces the segment endpoints intersect non-judgment and post-processing concave polygon method to solve the constraint for the concave side effects domain Polygons invalid, and to achieve constrained Delaunay triangulation.Experiments show that constrained Delaunay triangulation can be achieved when the constraint domain is concave polygon.The algorithm is efficient and has good robustness. The program can be easy to achieve.