基于图的DTAD的简易稳健自动生成算法

二维任意域(含任意多个空腔)的Delaunay三角剖分(简记为DTAD)广泛应用于有限元网格生成等方面。本文提出了一种基于图的DTAD的简易稳健自动生成算法。该算法首先构造任意域中所有边界点集的约束最小生成树,然后将同时满足本文所给三个简易约束算法的边逐次引入初始三角形网格表,形成边界点集的三角剖分,再通过稳健局部优化算法和贴体生成核插入算法自动生成DTAD。本文同时分析了退化及数值计算误差对剖分结果的影响,在提高局部优化的稳健性方面对该算法做了进一步完善,使之能更好地满足任意域网格剖分的要求。文末给出具体应用实例以说明本文所提算法的有效性。

A Simplified Robust Graph- based Automatic Delaunay Triangulation Algorithm for Arbitrary 2D Domain

There are some applications of Delaunay triangulation for arbitrary 2D (denoted as DTAD for short) domain (including some cava), such as generation of finite element meshes. This paper proposes a simplified robust graph-based automatic algorithm of DTAD.At first, the constrained minimum spanning tree for all boundary points is constructed. According to three simplified constrained algorithms, the triangle meshes for these points are obtained by inserting an edge every time. Then DTAD is constructed automatically by using the robust local optimization algorithm and the body-fitted generating kernel algorithm.At the same time the influences of degeneracy and numerical errors to triangulation quality are also analyzed. Robustness of the local optimization algorithm is greatly improved, so it can be better used for triangulation within arbitrary 2D domain. Numerical examples are also given to illustrate the effectiveness of the method at the end of the paper.