大家好，欢迎来到IT知识分享网。

Voronoi图是通过Delaunay三角网得到的，所以我们先来介绍一下Delaunay三角网的两个重要的性质：

Delaunay三角网是由一个一个的三角形构成的，其中三角形中的每一个顶点都是Voronoi点集中的点。

1、空外接圆性质：在由点集S构成的Delaunay三角网中，每个三角形的外接圆均不包含点集S中的其他任意点，即任何一个Delaunay三角形的外接圆不包含其他任何点。
2、最大的最小角性质：在由点集S所构成的三角网中，Delaunay三角网中三角形的最小角度是最大的，一个简明的解释：2个相邻三角形构成的凸四边形的对角线在相互交换后，6个内角的最小角不再增大。

下面给出Voronoi图的定义：

Voronoi图，又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Voronoi三角形是Delaunay图的偶图；

什么意思呢，我们通过一个例子看一下怎么通过Delaunay三角网得到Voronoi图：

三角形两边垂直平分线的交点就是外接圆的圆心，所以说找到所有三角形的外接圆圆心相连也就相当于 ”连接两邻点直线的垂直平分线组成的连续多边形“

对于给定的初始点集P，有多种三角网剖分方式（分治算法、数据点渐次插入算法、三角网生长算法），其中Delaunay三角网具有以下特征：
1、Delaunay三角网是唯一的；
2、三角网的外边界构成了点集P的凸多边形“外壳”；
3、没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。
4、如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。
Delaunay三角形网的特征又可以表达为以下特性：
1、在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；
2、在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；
3、形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；
4、不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。

这里有Voronoi更数学化的定义：

转自http://blog.csdn.net/saeba5566/article/details/6285959

Voronoi图的定义：

   1.设p，q是平面上的两个点，L是pq的中垂线，L将平面分为两个部分【L左】和【L右】，在【L】左内的点r有特性|pr|<|qr|，即位于【L左】内的点比平面其他点更接近p，不妨记H(p,q)=【L左】，同理H(q,p)=【L右】

   2.给定平面上n个点的点集S={p1,p2,……pn}。定义V(pi)是所有j(i!=j)的H(pi,pj)的交集，即V(pi)表示比其他点更接近于pi的电的轨迹是n-1个半平面的交，这是一个不多于n-1条边的凸多边形区域，称为关联于pi的Voronoi多边形（域）

   Voronoi图的特点：

   1.Vor(S)把平面划分成n个多边形域，每个多边形域V(pi)包含且只包含S的一个点pi。

   2.Vor(S)的边是S中某对点的中垂线的一个线段或者射线。

   3.V(pi)是无界的，当且仅当pi属于凸包外界的点集。

   4.Voronoi图至多有2*n-5个顶点和3*n-6条边。

   5.每个Voronoi点恰好是三条Voronoi边的交点（假如任何四点都不共圆的话）。也就是说Voronoi点就是形成三边的三点的外界圆圆心，而且所有的这些外界圆有个特点：各自内部不含任何S点集的点（空心圆）。

利用第5条性质就可以线性扫描Voronoi图，解决最大空心圆问题。

这里我是使用三角网生长算法来实现Voronoi图，下面介绍该算法：

Delaunay三角网生成

1、以任一点为起始点，找出与起始点最近的数据点相互连接形成Delaunay三角形的一条边作为基线。

2、按Delaunay三角网的判别法则(即它的两个基本性质)，找出与基线构成Delaunay三角形的第三点；

3、基线的两个端点与第三点相连，成为新的基线；

迭代以上两步直至所有基线都被处理。

上述过程表明，三角网生长算法的思路是，先找出点集中相距最短的两点连接成为一条Delaunay边，然后按Delaunay三角网的判别法则找出包含此边的Delaunay三角形的另一端点，依次处理所有新生成的边，直至最终完成（各种不同的实现方法多在搜寻“第三点”）

Voronoi生成

1、对三角形集合进行遍历，记录每个三角形是由哪三个点构成的。
2、计算每个三角形的外接圆圆心，并记录。
3、遍历三角形集合，寻找与当前三角形t三边共边的相邻三角形ta，tb和tc。
4、如果找到对应边的邻接三角形，则把寻找到的三角形的外心与t的外心连接，存入Voronoi边集合中。如果找不到，则求出该边所对应的中垂线射线与边缘的交点，将外心与其连线存入Voronoi边集合中。

Voronoi生成基本上一样，主要是三角网生成算法不同。

下图绿色的为生成的Delaunay三角网，红色的为Voronoi图（图来源自：https://blog.csdn.net/haney_2015/article/details/78773505）

源码：

链接：https://pan.baidu.com/s/1Yw3WStpA8bnHHKL5sNNdng
提取码：r1dh

另外还有两种生成维诺图的方法，原文链接：https://www.jianshu.com/p/172749e6116a?ivk_sa=1024320u

 

Delaunay三角剖分其实并不是一种算法，它只是给出了一个“好的”三角网格的定义，它的优秀特性是空圆特性和最大化最小角特性，这两个特性避免了狭长三角形的产生，也使得Delaunay三角剖分应用广泛。


空圆特性其实就是对于两个共边的三角形，任意一个三角形的外接圆中都不能包含有另一个三角形的顶点，这种形式的剖分产生的最小角最大。

假如以AC来剖分四边形ABCD，这里B点在三角形ACD的外接圆内，D点在三角形ABC的外接圆内，所以不具有空圆特性

以BD来剖分四边形ABCD，C点不在三角形ABD的外接圆内，A点也不在三角形BCD的外接圆内，具有空圆特性，而且它的最小角要比不满足空圆特性的最小角大。

 

问题描述

 

  现在给定了平面上的一个点集V，求出它的Delaunay三角剖分

 

Bowyer逐点插入法

还有一个这个算法的讲解：https://www.tqwba.com/x_d/jishu/186629.html

Bowyer逐点插入法是一个很经典的实现方法，网上的资料大多数都是采用的这种算法。这里使用的算法是按照 Paul Bourke在论文中提供的伪代码实现的，这个伪代码也写的很好，非常容易懂

subroutine triangulate input : vertex list 　　输入：顶点链表 output : triangle list　　输出：三角形链表 initialize the triangle list　　初始化三角形链表 determine the supertriangle　　确定超级三角形 add supertriangle vertices to the end of the vertex list　　 将超级三角形的顶点加入到顶点链表中 add the supertriangle to the triangle list　　将超级三角形加入到三角形链表中 for each sample point in the vertex list　　对顶点链表中的每一个点 initialize the edge buffer　　初始化边数组 for each triangle currently in the triangle list　　对于三角形链表中的每一个三角形 calculate the triangle circumcircle center and radius　　计算出外接圆圆心和半径 if the point lies in the triangle circumcircle then　　如果这个点在三角形的外接圆内 add the three triangle edges to the edge buffer　　把这个三角形的三条边加入到边数组中 remove the triangle from the triangle list　　从三角形链表中将这个三角形删除 endif endfor delete all doubly specified edges from the edge buffer　　把边数组中所有重复的边都删除，注意这里是把所有的重复边都删除，比如有边e1,e2,e2,e3，删除后应该只剩e1和e3 this leaves the edges of the enclosing polygon only　　这步会得到一个闭合的多边形 add to the triangle list all triangles formed between the point 用这个点和边数组中的每一条边都组合成一个三角形，加入到三角形链表中 and the edges of the enclosing polygon endfor remove any triangles from the triangle list that use the supertriangle vertices从三角形链表中删除使用超级三角形顶点的三角形 remove the supertriangle vertices from the vertex list将超级三角形的顶点从顶点链表中删除 end

在使用过程中，发现“把超级三角形的顶点加入到顶点链表中”似乎没什么必要，另外，顶点用数组存好一点，因为不需要添加和删除。

以四个点A、B、C、D举例，首先建立一个超级三角形PQR，这个三角形要把所有点都包含进去。

 

 接着分析A点，因为A点在三角形PQR的外接圆内部，所以利用A点将三角形PQR分拆成三个子三角形。

 

 再考虑Ｂ点，它只在三角形AQR的内部，再将三角形AQR分拆成三个子三角形。

 

 

接着是C点，这时我们有5个三角形，对这5个三角形每一个检查C点在不在它的外接圆内。经过检测，发现它在三角形APR和三角形ABR的外接圆内。

 

 

 删除三角形APR和三角形ABR的公共边AR，得到四边形ABPR，并将C点与每一个边组成一个三角形。

 

 最后对D点进行分析，它在三角形ABC和三角形BCR的外接圆内，所以应删除公共边BC，再用D点与这两个三角形的其他边形成子三角形。

 

 

 

 最后把含有超级三角形的顶点的三角形全部删除，就得到这四个点的三角剖分

 

 我编写程序的时候使用三个点进行测试，有时候结果出不来，是因为在最后一步删除超级三角形的时候是这样的

然后删除超级三角形相关顶点就把所有三角形都删掉了。刚开始的时候我以为是和超级三角形的选取有关，纸异兽的文章中也没有详细分析，只提供了一个生成超级三角形的方案。我很好奇这个超级三角形只要包含所有点就可以吗，后来发现当遇到只有三个点的情况就直接相连就可以了，四个点以后就不会出现这种情况。

另外关于这个方法，我在Github上看到了一个实现，作者是jeanbroid，用openGL做显示，里面用了很多C++标准库的东西，让我大开眼界，非常感谢他，不过他用到了双缓存，需要把demo.cpp中的GLUT_SINGLE改成GLUT_DOUBLE才能运行。

分治法

分治法是我在查看维基百科的时候看到的，据维基百科说分治法是效率最高的一种方法。在维基百科的引用中发现了一个介绍delaunay三角剖分的分治法的一个非常好的网站，网站作者是Samuel Peterson，这个网站主要介绍了在给定条件下的Delaunay三角剖分。

分治法进行三角剖分需要对点集中所有点按照x坐标的升序进行排序，x坐标相同时，按照y坐标进行排序，接着将整个点集递归地划分数量相近的两个子集，直到子集中点的数目小于等于3。

先给出一个定义方便后面叙述。对于一条边，如果它的两个端点都在分割线的左边，称它为LL边，一端在左边一端在右边称为LR边，两个端点都在右边称为RR边。

  分治法的重点在于如何递归地合并三角网格。
  首先是确定一条LR基线，这条线位于最下方，且不与其他边相交，如27边

接着，确定下一条LR边。以右侧三角网为例，按照顺时针方向，计算出∠672，∠872，∠1072，∠972的值，并根据角度大小对顶点进行排序，角度最小的点为第一候选点，以此类推，这里第一候选点为6，第二候选点为8。

 

 

作三角形276的外接圆，发现第二候选点8不在该外接圆内，且∠672小于180°，故右侧的候选点为6。候选点的要求是以候选点与该侧基线端点形成的角小于180°，且不包含下一候选点。若大于180°，则该侧无候选点，若包含下一候选点，则考虑下一候选点是否满足该条件。按照这种方法对左侧三角网格进行分析，可得到左侧候选点为点3。

当左右两侧都存在候选点时，如当前情况，这时需要考虑下一条LR边是37还是26。作三角形237的外接圆，可发现右侧候选点6在此外接圆外，而左侧候选点在三角形276外接圆内，故下一条LR边为边37。

　　当只有一侧存在候选点时，将此候选点与基线另一侧的端点连线作为下一条LR边。

  将边37作为下一条基线重复该过程，直到两边都不存在候选点，程序结束。

项目源代码👉 https://github.com/earthwjl/DelaunayTriangulate