Reprint of: Delaunay refinement algorithms for triangular mesh generation
Reprint of: Delaunay refinement algorithms for triangular mesh generation
复制标题
DOI：
10.1016/j.comgeo.2014.02.005
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
J. Shewchuk
中科院分区：
文献类型：
--
作者：
J. Shewchuk
Delaunay精化是一种生成非结构化三角形网格的技术，用于插值、有限元法和有限体积法。在理论和实践中，Delaunay细化生成的网格在角度、边长、三角形数量和三角形从小到大的分级上都满足有保证的界限。本文提出了一个直观的分析Delaunay细化算法的框架，该框架统一了L. Paul Chew和Jim Ruppert的开创性网格生成算法，并在几个较小的方面对算法进行了改进，最重要的是，它有助于解决小角度非流形域的网格划分难题。虽然不能去除输入几何中固有的小角，但人们希望在不创建任何新的小角的情况下对一个域进行三角剖分。不幸的是，这个问题并不总是可以解决的。妥协是必要的。提出了一种Delaunay改进算法，该算法可以创建一个网格，其中大多数角度为30°或更大，并且没有任何角度小于arcsin [(3/2) sin （ϕ/2）] ~ （3/4） ϕ，其中φ≤60°是分隔输入域两个部分的最小角度。小于30°的新角度只出现在小于60°的输入角附近。在实际应用中，该算法的性能优于这些边界。另一个新的结果是，Ruppert的分析技术可以用来重新分析Chew的算法之一。Chew证明了他的算法不会产生小于30°的角（排除小的输入角），但不能保证三角形的分级或数量。他推测他的算法提供了这样的保证。他的猜想在这里得到了有条件的证实：如果角度界限放松到小于26.5°，Chew的算法产生的网格（没有小输入角的域）是分级和尺寸最优的。
Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles. Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin [(3/2) sin (ϕ/2)]∼(3/4) ϕ, where ϕ⩽ 60° is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest. Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30°(barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.