Delaunay三角网

Delaunay三角网"/>

Delaunay三角网

Delaunay三角网概述

1 三角网格网络概述

网格主要用于计算机图形学中，有三角、四角网格等很多种。计算机图形学中的网格处理绝大部分都基于三角网格来模拟复杂物体的表面，如建筑、车辆、动物等。

三角形表示网格也叫三角剖分。三角网格稳定性强、结构简单，可以非常方便并且快速生成，在非结构化网格中最常见。而且相对于一般多边形网格，许多操作对三角网格更容易。

不规则三角网(TIN, Triangulated Irregular Network)模型采用一系列相连接的三角形拟合地表或其他不规则表面，常用来构造数字高程模型，常用的TIN生成方法是Delaunay 剖分方法。

2 Delaunay 三角剖分

前苏联数学家 Delaunay于1934年提出，对于任意给定的平面点集，该方法遵循“ 最小角最大 ” 和“ 空外接圆 ” 准则进行剖分。

Delaunay 三角网是Voronoi图的伴生图形，通过连接具有公共顶点的三个V n多边形的生长中心而生成的, 这个公共顶点就是形成的Delaunay三角形外接圆的圆心。

2.1 性质

① 空外接圆，三角形的外接圆不包含这个面域的其他任何点；

满足Delaunay条件，三角形的顶点都不在其他三角形的外接圆内
② 最小角最大，最小角之和均大于任何非 Delaunay剖分所形成三角形最小角之和 。每两个相邻的三角形构成的凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。

2.2 存储和表示

在Delaunay三角网中的每个三角形平面的几何特征完全由三个顶点的空间坐标值（x,y,z）所决定。存储的时候，每个三角形分别构成一个记录，每个记录包括：三角形标识码、该三角形的相邻三角形标识码、该三角形的顶点标识码等，顶点的空间坐标值则另外存储。

直接以每个顶点表示三角形会有冗余和维护难度大的问题，

所以，OBJ, OFF, WRL等文件顶点一般用标识码表示。

注意，为了方向矢量计算，三顶点一般以右手法则逆时针顺序存储。

3 Delaunay 网点添加

对于生成三角网的过程，在已经生成的三角网中插入新的点，会导致新三角网不再符合三角形剖分准则，一般采用局部优化算法(LOP)。该方法法交换凸四边形的对角线，保留短的那条对角线，使三角网中所有三角形的最小角度最大化。插入新的点集时，检测新三角形及其临近三角形，使其符合三角剖面即可。

4 TIN生成方法

按照2012年论文《Delaunay 三角网通用合并算子及分治算法的简化》，TIN生成方法包括：三角网扩张法、增点法、分治法和扫描线法，其中分割-归并法、三角网生长法是普遍采用的算法：

分割-归并，递归地分割点集至足够小，使其易于生成三角网，然后把子集中的三角网合并，经优化 生成最终的三角网。该算法时间效率高，但大量递归运算占用内存空间较多；

三角网生长法，先找出点集中最近两点连接成一 条边，然后按 Delaunay 三角网的判别法则找出第三点，再依次处理全部区域。该算法占用内存空间较小，但时间效率较低。

4.1 分割合并算法

采用分而治之策略，先将数据点分割成易于三角化的点子集，后对每个子集分别三角化，并由LOP优化成三角网；之后对每个子集的三角网进行合并，形成最终的三角网。

4.2 逐点插入算法

先形成整个数据空间的边界，然后逐步缩小

4.3 递归生长算法

扩张生长法，从第一个三角形开始向外层层扩展，以递归生长法为代表

5 编程实现：

5.1 Lawson局部最优化（LOP)：

将两个具有公共边的三角形合并成一个凸多边形；
以最大空外接圆为准则，观察第四个顶点是否在三角形的外接圆之内；
如果在，修正对角线，对调对角线，优化结束

5.2 逐点插入法

基本原理：

建立一个大的多边形，将所有数据点包围起来，插入一点，将其和所在三角形三个顶点进行连接，形成三个新的三角形，对于新三角形进行空外接圆检测，局部最优处理；

基本步骤：

(1) 构造一个超级三角形，包含了所有数据点，放入三角形list；

(2) 将数据点逐个加入，找到该点所在的三角形，将该点和所在三角形顶点进行连接，构成三个小三角形；

(3) 计算每个小三角形的外接圆：

如果外接圆中均不包含其他点，则进入下一步，插入新顶点；
如果某个小三角形中包含其他顶点（四个点，两个具有一个公共边的三角形），互换对角线以形成新的三角形，检查新三角形中是否包含其他点，直至所有的都满足空外接圆的条件；
(4) 循环执行上述第二步，直至所有的数据点插入完毕，最后删除超级三角形关联的三角形即可；

Bowyer-Watson 算法关键步骤
二维效果：

三维：

有说法是可以先转为二维处理