A 2D advancing-front Delaunay mesh refinement algorithm

摘要

I present a generalization of Chew's first algorithm for Delaunay mesh refinement. I split the line segments of an input planar straight line graph (PSLG) such that the lengths of split segments are asymptotically proportional to the local feature size at their endpoints. By employing prior algorithms, I then refine the truly or constrained Delaunay triangulation of the PSLG by inserting off-center Steiner vertices of "skinny" triangles while prioritizing triangles with shortest edges first. This technique inserts Steiner vertices in an advancing front manner such that we obtain a size-optimal, truly or constrained Delaunay mesh if the desired minimum angle is less than 30 degrees (in the absence of small input angles). This is an improvement over prior algorithms that produce size-optimal meshes with minimum angles of about 26.4 degrees and 28.6 degrees for truly and constrained Delaunay meshes, respectively. Even in the presence of small input angles, the upper bound on the maximum angle is an angle strictly greater than 120 degrees (an improvement from about 137 degrees). The lower bound on the minimum angle in the presence of small angles is identical to prior bounds. (C) 2021 Elsevier B.V. All rights reserved.