A 2D advancing-front Delaunay mesh refinement algorithm

DOI10.1016/J.COMGEO.2021.101772MaRDI QIDQ2230400zbMATH OpenOpenAlexFDO

Authors Shankar P. Sastry

Publication date 17 September 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.01539

zbMATH Keywords

advancing-front meshesDelaunay mesh refinementsize-optimal meshes

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50)

Abstract: I present a generalization of Chew's first algorithm for Delaunay mesh refinement. In his algorithm, Chew splits the line segments of the input planar straight line graph (PSLG) into shorter subsegments whose lengths are nearly identical. The constrained Delaunay triangulation of the subsegments is refined based on the length of the radii of the circumcircles of the triangles. This algorithm produces a uniform mesh, whose minimum angle can be at most $pi/6$. My algorithm generates both truly Delaunay and constrained Delaunay size-optimal meshes. In my algorithm, I split the line segments of the input PSLG such that their lengths are asymptotically proportional to the local feature size (LFS) by solving ordinary differential equations (ODEs) that map points from a closed 1D interval to points on the input line segments in the PSLG. I then refine the Delaunay triangulation (truly or constrained) of the PSLG by inserting off-center Steiner vertices of "skinny" triangles while prioritizing such triangles with shortest edges first. As in Chew's algorithm, I show that the Steiner vertices do not encroach upon any subsegment of the PSLG. The off-center insertion algorithm places Steiner vertices in an advancing front manner such that we obtain a size-optimal Delaunay mesh (truly or constrained) if the desired minimum angle is less than $pi/6$. In addition, even in the presence of a small angle $phi<pi/2$ in the PSLG, the bound on the minimum angle "across" the small angle tends to $arctan((sinphi)/(2-cos(phi))$ as the PSLG is progressively refined. Also, the bound on the maximum angle across any small input angle tends to $pi/2+phi/2$ as the PSLG is progressively refined.

Review text

This article discusses a generalization of Chew's first algorithm for Delaunay mesh refinement. The approach relies on generating well-graded meshes by refining the planar straight line graph such that the lengths of the split segments are asymptotically proportional to the local feature size at the end points of the split segments. Further, the Steiner vertices are inserted in an advancing front manner in order to obtain a size-optimal, truly or constrained Delaunay mesh.

Recommendations

• Delaunay refinement algorithms for triangular mesh generation
• scientific article; zbMATH DE number 437532
• Fully Generalized Two-Dimensional Constrained Delaunay Mesh Refinement
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• DELAUNAY REFINEMENT ALGORITHMS FOR ESTIMATING LOCAL FEATURE SIZE IN 2D AND 3D

Cites work

• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• Data Structures for Mobile Data
• Delaunay refinement algorithms for triangular mesh generation
• Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm
• Fully Generalized Two-Dimensional Constrained Delaunay Mesh Refinement
• Generalized two-dimensional Delaunay mesh refinement
• scientific article; zbMATH DE number 437532 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1501063 (Why is no real title available?)
• scientific article; zbMATH DE number 1515661 (Why is no real title available?)
• Kinetic hanger
• LATIN 2004: Theoretical Informatics
• Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations
• ON GOOD TRIANGULATIONS IN THREE DIMENSIONS
• On the Angle Condition in the Finite Element Method
• Quality Triangulations with Locally Optimal Steiner Points
• WHEN AND WHY DELAUNAY REFINEMENT ALGORITHMS WORK

Cited in

(19)

• An improved procedure for 2D unstructured Delaunay mesh generation
• On the sizes of Delaunay meshes
• Fully Generalized Two-Dimensional Constrained Delaunay Mesh Refinement
• scientific article; zbMATH DE number 6830774 (Why is no real title available?)
• scientific article; zbMATH DE number 1501518 (Why is no real title available?)
• Parametric surface meshing using a combined advancing-front generalized Delaunay approach
• Global balancing of a triangular mesh
• WHEN AND WHY DELAUNAY REFINEMENT ALGORITHMS WORK
• A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
• Meshes preserving minimum feature size
• A time-optimal delaunay refinement algorithm in two dimensions
• An algorithm of combining of advancing front and delaunay triangulation to 3-D domain tesselation
• Size Competitive Meshing Without Large Angles
• Interleaving Delaunay refinement and optimization for 2D triangle mesh generation
• A time efficient Delaunay refinement algorithm
• Geometrical Mesh Improvement Properties of Delaunay Terminal Edge Refinement
• Where and how Ruppert's algorithm fails
• Combining improvement and refinement techniques: 2D Delaunay mesh adaptation under domain changes
• Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations

Describes a project that uses

Uses Software

• Triangle

This page was built for publication: A 2D advancing-front Delaunay mesh refinement algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230400)