An improved Lepp based, terminal triangles centroid algorithm for constrained Delaunay quality triangulation is discussed and studied. For each bad quality triangle t, the algorithm uses the longest edge propagating path (Lepp(t)) to find a couple of Delaunay terminal triangles (with largest angles less than or equal to 120°) sharing a common longest (terminal) edge. Then the centroid of the terminal quadrilateral is Delaunay inserted in the mesh. Bisection of some constrained edges are also performed to assure fast convergence. We prove algorithm termination and that a graded, optimal size, 30° triangulation is obtained, for any planar straight line graph (PSLG) geometry with constrained angles greater than or equal to 30°.
展开▼
