IKCEST

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.

Original Text (This is the original text for your reference.)

Terminal Triangles Centroid Algorithms for Quality Delaunay Triangulation

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.

+More

Keywords

non constrained angles planar straight line graph pslg geometry optimal size 30 degrees triangulation quality delaunay triangulation terminal quadrilateral terminal triangles centroid delaunay algorithm midpoints of lepp algorithms pslg geometries nonimprovable triangles mesh processing order longest edge propagating path

Cite this article

APA

MLA

Chicago

Javier Díaz,Maria-Cecilia Rivara,.Terminal Triangles Centroid Algorithms for Quality Delaunay Triangulation. (),102870.

Language

International

Translate engine

Article's language

Action

Recommended articles

Report