理解2D三角剖分

作为一个野生新手。可能理解会有许多不正之处。如果大佬们看到了还请一定多多批评啊！

虽然本博可能讲的不甚专业，但是对于新手说，应该比较容易入门吧。因为我也是新手的视角来理解这个东西的。

三角剖分

什么是三角剖分？其实就是把离散集合剖分成不均匀的三角网格，直观的表示就是：

理解2D三角剖分

你看，我们把这些离散的点用三角网格串起来了，现在它们就是有关系的点了，甚至可能牵一发而动全身。

那么三角剖分专业性的定义是什么？

【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段，E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：

1、除了端点，平面图中的边不包含点集中的任何点。

2、没有相交边。也就是说边和边之间没有交叉点。

3、平面图中的所有面都是三角面，且所有三角面的合集是散点集V的凸包。

ps：凸包–>用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外的点连接起来构成的凸多边形，它能包含点集中的所有点。

Delaunay三角剖分

说的德劳内三角剖分就是它啦。在实际运用中最多的三角剖分也就是Delaunay三角剖分。它是一种特殊的三角剖分。先从Delaunay边说起：

【定义】Delaunay边：假设E中的一条边e(两个端点为a,b)，e若满足下列条件，则称之为Delaunay边：存在一个圆经过a，b两点，圆内不含点集V中任何其他的点(注意是圆内，圆上是可以三点共圆的)，这一特性又称空圆特性。

【定义】三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

看到这里，你可能会以为Delaunay三角剖分其实就是两个端点的圆，没有其他点在圆内。其实不是呀。还有“只包含呢”。所以Delaunay三角剖分的准则有两条。

Delaunay三角剖分的准则

1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其他点存在。如下图所示：

理解2D三角剖分

可以看到ADC和ABC这两个三角形的外界圆都只有自己的三个顶点。

2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的”三角网。具体的说是在两个相邻的三角形构成凸四边形的对角线，在相互交换后，两个内角的最小角不再增大。如下图所示：

理解2D三角剖分

这个我没太搞清楚。这个有什么用呢？有人说这个既能保证剖分的唯一性(凸四边形的剖分唯一)，又能保证剖分的最优性(想像一下如果剖分出现很大的钝角，那么计算机计算三角形面积的时候误差会相当大)。

Delaunay三角剖分的特性

1、最接近性：以最接近的三点形成三角形，且各线段皆不相交。

2、唯一性：不论从区域何处开始构建，最终都将得到一致的结果。

3、最优性：任意两个相邻三角形构成的凸四边形的对角线如果可以互换，那么两个三角形六个内角中最小角度不会变化。

4、最规则：如果将三角网中的每个三角形的最小角进行升序排列，那么Delaunay三角网的排列得到的数值最大。

5、区域性：新增、删除、移动某一个顶点只会影响临近的三角形。

6、具有凸边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。

ps：这些特性非常重要！！！！！！一定要理解，一定要看完。

思考：如何从普通的三角剖分转成Delaunay三角剖分呢？这里就要介绍LOP算法—–局部最优化处理。

理论上为了构造Delaunay三角网，Lawson提出的局部优化过程LOP(Local Optimization Procedure)，一般三角网经过LOP处理，即可确保为Delaunay三角网，其基本做法如下所示：

1、将两个具有共同边的三角形合成一个多边形。

2、以最大空圆准则作为检查，看其第四个顶点是否在三角形的外接圆内。

3、如果在，修正对角线即将对角线对调，即可完成局部优化过程的处理。

LOP处理过程如下图所示：

理解2D三角剖分

OK，那前面的理论说完了。下面就要说一下，常见的Delaunay剖分算法有哪些。从研究者开始研究到现在，实现三角剖分的算法有很多。但是最常见的就是Lawson算法和Bowyer-Watson算法。

Lawson算法

这是一个逐点插入算法。是Lawson在1977年提出的，该算法的思路简单，容易编程实现。基本思想为：

首先建立一个大的三角形或多边形，把所有的数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐点对它们进行空外接圆检测，同时用Lawson设计的局部优化LOP进行优化，即可通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。

这个基于散点的构网算法理论严密，唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，遇到非Delaunay边删除即可。在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网。

但在实际应用中，这种构网算法当点集较大时构网速度较慢，如果点集范围是非凸区域或者存在内环，就会产生非法三角形。

Bowyer-Watson算法

目前采用逐点插入方式生成Delaunay三角网的算法主要基于Bowyer-Watson算法，该算法的基本思想：

这一算法的关键的第2步图示如下：

理解2D三角剖分

https://github.com/ironwallaby/delaunay 这个代码的效果是这样的：

理解2D三角剖分

它的伪代码：

input: 顶点列表(vertices)　　　　　　　　　　　　　　　　　　　　 　//vertices为外部生成的随机或乱序顶点列表 output:已确定的三角形列表(triangles) 　　　　初始化顶点列表 　　　　创建索引列表(indices = new Array(vertices.length))　　　　//indices数组中的值为0,1,2,3,......,vertices.length-1 　　　　基于vertices中的顶点x坐标对indices进行sort　　 　　　　　 //sort后的indices值顺序为顶点坐标x从小到大排序（也可对y坐标，本例中针对x坐标） 　　　　确定超级三角形 　　　　将超级三角形保存至未确定三角形列表（temp triangles） 　　　　将超级三角形push到triangles列表 　　　　遍历基于indices顺序的vertices中每一个点　　　　　　　　　 　//基于indices后，则顶点则是由x从小到大出现 　　　　　　初始化边缓存数组（edge buffer） 　　　　　　遍历temp triangles中的每一个三角形 　　　　　　　　计算该三角形的圆心和半径 　　　　　　　　如果该点在外接圆的右侧 　　　　　　　　　　则该三角形为Delaunay三角形，保存到triangles 　　　　　　　　　　并在temp里去除掉 　　　　　　　　　　跳过 　　　　　　　　如果该点在外接圆外（即也不是外接圆右侧） 　　　　　　　　　　则该三角形为不确定 　　　　　　　　　 //后面会在问题中讨论 　　　　　　　　　　跳过 　　　　　　　　如果该点在外接圆内 　　　　　　　　　　则该三角形不为Delaunay三角形 　　　　　　　　　　将三边保存至edge buffer 　　　　　　　　　　在temp中去除掉该三角形 　　　　　　对edge buffer进行去重 　　　　　　将edge buffer中的边与当前的点进行组合成若干三角形并保存至temp triangles中 　　　　将triangles与temp triangles进行合并 　　　　除去与超级三角形有关的三角形 end

用图来解释一下伪代码的过程：

随机的三个点

理解2D三角剖分