Constrained Delaunay Parallel Algorithm Based on Cutting

Constrained Delaunay triangulation plays an important role in image recognition, finite element analysis, map synthesis and other fields, so it has attracted the attention and research of many scholars. However, the current constraint Delaunay algorithm is greatly limited by the increase of constraints. Therefore, this paper proposes a Constrained Delaunay Parallel Algorithm Based on Cutting (CDPAC), which controls the growth direction of the triangular grid so that the generated triangle can divide the entire point set, thereby transforming the triangulation of one point set into the triangulation of two independent point sets. The rate is improved by calculating the triangulation of the two submaps in parallel. Experimental results show that the Triangulated Irregular Network (TIN) obtained by the proposed algorithm is consistent with the original algorithm, but its speed is better than that of the original algorithm, and with the increase of the number of point sets and constraints, the speed advantage is also more obvious.