在上期的推文《常用的有限元网格生成方法（上）》中，小编为大家介绍了映射法(Mapping)和四（八）叉树法 (Quadtree/Octree)。

本周我们继续发放”干货“，为大家带来Delaunay三角化法 (Delaunay Triangulation)和前沿推进法 (Advancing Front Technique)这两种有限元网格生成方法。

谈到Delaunay三角化的来历，就不得不先提它的对偶图——Voronoi图。1908年，俄国数学家Voronoi提出：给定平面内点集Q，对于其中每个点p，存在一个区域，该区域内的任意一点与p的距离是与Q中所有点距离的最小值，这些区域的合集构成Q的Voronoi图。1934年Delaunay提出，通过连接Voronoi图相邻区域的点，可以得到一个平面点集的三角化，这样的三角化就称作该点集的Delaunay Triangulation，简称DT。

（Voronoi图与Delaunay三角化）

给定一个平面点集Q，其DT有以下特性：

1. 唯一性：在不考虑四点共圆的情况下，DT是唯一的；

2. 更大化最小角：在Q的所有三角化中，DT使最小角达到更大；

3. 空圆特性：DT中每个三角形单元的外接圆都不包含其它节点，此特性也称为DT条件，可用于判断三角化是否为DT，如下图所示。此外，通过简单的边翻转（BD->AC）可将局部非DT转化为DT。

（边翻转示意图）

也就是说，DT避免了生成小内角的长薄单元，尽可能地将所有三角形趋向均匀。鉴于其良好的特性，到了上世纪80年代，DT开始大量应用于有限元的网格生成，出现了许多DT的生成算法，最常见的当属Bowyer-Watson算法。Bowyer-Watson算法采用逐点插入法，每次插入新点后，都要保证当前的三角化符合DT条件。此外，点集的插入顺序是影响生成算法效率的重要因素，一般采用随机次序插入。Bowyer-Watson算法的主要步骤如下：

1. 插入一个新点，在已生成的三角形中找出所有外接圆包含插入点的三角形，得到影响区域多边形；

2. 删除多边形的内部边，连接插入点与多边形的全部顶点，连接前需要进行可见性检查。

（Bowyer-Watson算法示意图）

DT生成算法对凸区域十分有效，然而待剖分区域很有可能在局部是凹的，凹区域采用DT方法生成的网格不能保证边界的完整性，需要进行边界恢复。对二维而言，可以通过简单的边翻转操作恢复边界。若AB是丢失的边界，循环多边形的每对相邻三角形构成的四边形进行边翻转判断，确保四边形的对角线不会穿过AB，直至多边形内的所有三角形都不穿过AB即可。

（二维边界恢复示意图）

综上，二维的Delaunay三角化法的基本步骤如下：

1. 得到待剖分区域的点集，包括边界节点和内部节点；

2. 将点集中的点生成一个随机插入次序；

3. 创建一个能包含点集凸包的三角形或正方形；

4. Bowyer-Watson算法，确保每一步都满足DT条件；

5. 通过拓扑操作恢复边界。

Delaunay三角化在由二维推广至三维的时候却遇到了一些问题。首先，三维Delaunay三角化会产生四个节点几乎共面的薄元，薄元的单元质量很差却能符合三维的DT条件。此外，三维的边界恢复不能直接由二维推广，需要分别针对边界边和边界面进行处理。不过随着研究的深入，这些问题目前都已经有了较好的解决办法。

前沿推进法也叫波前法，由Lo和Lohner提出，是一种基于边界的全自动非结构化网格生成方法。顾名思义，该方法将区域边界作为初始波前，根据一定规则向区域内部推进，推进的过程中进行网格生成，当所有波前在区域内部聚合消失，网格生成完毕。与Delaunay三角化法具有成熟的理论依据不同，前沿推进法的推进规则在很多情形下是依靠经验制定的，但这并不妨碍它的成功应用。前沿推进法的算法时间复杂度与四（八）叉树法和Delaunay三角化法相当，并且生成的网格在边界处有更好的质量。

以二维为例，前沿推进法的基本步骤如下：

1. 将待剖分区域边界离散化，得到一组线段集合，即初始前沿；

2. 根据前沿各线段的位置关系和推进规则生成新节点，并与前沿线段连接得到新的单元，并更新前沿中的线段；

3. 重复步骤2，直至前沿为空，剖分完成。

（前沿推进法示意图）

前沿推进法的优势在于新节点和新单元同时生成，便于利用已存在的单元控制后续生成的节点位置，以达到质量控制、局部加密或网格过渡的要求。此外，从边界向内推进，能够优先保证边界附近的单元质量。

不过，前沿数据结构的设计一直是此方法的难点。一方面要考虑推进规则的完整性；另一方面，在生成新单元时要进行大量的相交判断、距离判断，需要尽可能减少执行判断的次数以提升剖分效率。

（二维前沿推进法的一种推进规则）

就算法的时间复杂度而言，四（八）叉树、Delaunay三角化法和前沿推进法这三种全自动的非结构化网格生成方法计算效率都为O(nlogn)，难分伯仲。但实际上各种网格生成方法都有各自的优势和局限性，在实际的网格生成算法中，往往需要将多种方法组合运用，扬长避短，以达到更好的剖分效果。