Terminal Triangles Centroid Algorithms for Quality Delaunay Triangulation
Artículo

Open/ Download
Access note
Acceso Abierto
Publication date
2020Metadata
Show full item record
Cómo citar
Rivara Zúñiga, María Cecilia
Cómo citar
Terminal Triangles Centroid Algorithms for Quality Delaunay Triangulation
Author
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 delta 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 delta (longest edge <= 5). In practice the algorithms behave as predicted by the theory.
Patrocinador
Departament of Computer Science, University of Chile
Indexation
Artículo de publicación ISI Artículo de publicación SCOPUS
Quote Item
Computer-Aided Design 125 (2020) 102870
Collections
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile
Related items
Showing items related by title, author, creator and subject.
-
Díaz Palacios, Javier Ulises (Universidad de Chile, 2018)La triangulación de Delaunay es una entidad geométrica con muchas aplicaciones en computación gráfica e ingeniería. Por lo general, su construcción es un problema difícil que a menudo viene acompañado con restricciones ...
-
Dávila Bonczos, Juan; Pino Manresa, Manuel del; Dipierro, Serena; Valdinoci, Enrico (Elsevier, 2016)We construct codimension 1 surfaces of any dimension that minimize a periodic nonlocal perimeter functional among surfaces that are periodic, cylindrically symmetric and decreasing. These surfaces may be seen as a ...
-
Alonso Ortega, Rodrigo Ignacio (Universidad de Chile, 2016)En el campo de la cosmología, los vacíos son regiones del espacio cuya densidad es nota- blemente menor que la densidad de fondo, abarcando distancias en el rango de 20 50 Mpc/h (1 Mpc/h ∼ 2,10 × 1019 km). Los primeros ...