Delaunay 三角刨分

德劳内三角刨分

Delaunay 三角形划分方法，是将平面上一组已给定的点连成三角形的方法，这些连接而成的点具有一些特点

如上图所示，左边的三角形满足第三点，每个三角形的外接圆只包含该三角形的三个点。右边的三角形不满足第三点，一个三角形外接圆包含除了三角形三点之外的其他点

Delaunay 三角形的优点

三角形中最小角最大，三角形内角和 180°，有三个角，那么最小角最大是 60°，也就是正三角形

首先给出确定的点集合 1~5，根据这些点可以有 a、b、c 三种构成三角形的方法

a、b 两种构建方法不符合外接圆的要求，c 的最小角最大并且满足外接圆要求

已经构建完 Delaunay 三角后新增点

以上图为例，原本通过 1~8 构成完毕，现在想要新增一个点 Q 到集合中

通过外接圆找到需要修改的三角形	连接空腔各个顶点

对于上图，给定了 1~5 点，6为预先给出的内点

参考点 4 的加入，也就是从 d -> e 的过程

在图 d 中，考虑加入点 4 时，有四个三角形 (017、173、738、123) 的内切圆中包含了点 4，所以去除了 17、13、37 三个边，并重新连接得到图 e

一个点加入时，公共线不一定只有一条

最后将辅助边和辅助点(0、7、8、9)都删掉

此时按照前面的方法，再加入点 6，得到最终结果

为什么需要向已经初始化的 Delaunay 设点？因为仅用边界点生成的 Delaunay 三角网格可能出现网格疏密与边界不一致（边界密集、内部稀疏），也可能出现过于扁平的三角形（最小角接近0°）导致数值计算不稳定

向初始化的 Delaunay 三角形内加点的过程是生成非结构网格的关键步骤，需要满足三个基本要求

第 2 点，其实就是期望边界密度自然传递至内部

为了完成上述要求，引入两个几何参数

长度标尺

长度标尺是赋予网格点的一个几何参数。对边界上的网格点及内部的网格点的长度标尺做以下定义

以上图为例，设 Q 是要插入到三角形145 中的一点，Q的长度标尺 L(Q) 表示如下

$$ L(Q) = \frac{L(1)/l_1 + L(4)/l_4 + L(5)/l_5}{1/l_1 + 1/l_4 + 1/l_5} $$

L(1)、L(4)、L(5) 是边界网格点的长度标尺，l1、l4、l5 是 Q 点到三顶点的距离

三角形外接圆的无量纲半径

设任意一个 Delaunay 三角形为 k，其外接圆的半径为 r(k)，其外接圆的圆心长度标尺为 L(Q)，其外接圆无量纲半径 R(k)

$$ R(k) = \frac{r(k)}{L(Q)} $$

接下来需要添加内点