Terminal Triangles Centroid Algorithms for Quality Delaunay Triangulation. (August 2020)

• Record Type: Journal Article
• Authors: Rivara, Maria-Cecilia; Diaz, Javier
• Is Part Of: Computer aided design. Volume 125(2020)
• Publication Date: 2020-08
• Subjects: Lepp algorithms -- Lepp Delaunay centroid algorithms -- Quality Delaunay triangulation -- Terminal triangles centroid -- Delaunay terminal triangles -- Delaunay terminal edges; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2020.102870
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Two Lepp algorithms for quality Delaunay triangulation are discussed. Firstly a terminal triangles centroid Delaunay algorithm is 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 degrees) sharing a common longest (terminal) edge. Then the centroid of the terminal quadrilateral is Delaunay inserted in the mesh. Insertion of the midpoints of some constrained edges are also performed to assure convergence close to the constrained edges. We prove algorithm termination and that a graded, optimal size, 30 degrees triangulation is obtained, for any planar straight line graph (PSLG) geometry with constrained angles greater than or equal to 30 degrees. We also prove that the size of the final triangulation is optimal and that this size is independent of the processing order of the bad triangles in the mesh. Next, by introducing the concept of non-improvable triangles (with constrained angle < 30 degrees), we generalize the algorithm to deal with PSLG geometries with N small constrained angles. Thus given a triangle size parameter δ for non-improvable triangles, the generalized algorithm constructs a quality triangulation with non constrained angles ≥ 30 degrees and at most N non-improvable triangles of size δ (longest edge ≤ δ ). In practice the algorithms behave as predicted by the theory. Graphical abstract: Highlights: Lepp based algorithms for quality triangulation. Order independent, optimal size triangulation algorithms. Terminal triangles Delaunay centroid insertion algorithm. Algorithms extended for small constrained angles. 30 degrees triangulation guaranteed, for PSLG geometries with constrained angles greater than or equal to 30 degrees.