A Local Adjustment Algorithm for Inserting Constrained Segments in Delaunay Triangulation

An algorithm for constructing constrained Delaunay triangulation (CDT) is presented. First, the Delaunay triangulation for constrained data sets is constructed. Then, by inserting constrained segments into the Delaunay triangulation, a local adjustment ismade to its impact area on the maximumangle principle on the condition that the basic properties of CDT are satisfied. Meanwhile, the process of inserting the constrained segments into CDTis expounded in detail, and the updatingmethod for the topological relations in CDTis presented. Finally, the time efficiency of the algorithmproposed is analyzed. It is shown that the algorithm has a high efficiency and a stable operation.