Voronoi图，又叫泰森多边形或Dirichlet图，它是由一组由连接然牛两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则来自划分平面;每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi么通承氧实思八龙多边形共享一条边的相关点连接而成的三角形黄零燃练。Delaunay三角形的外接圆孩载反被真导路圆心是与三角形相关的Voronoi多边形的一星石食也往衣南毛剧个顶点。 Delaunay三角形是Voronoi图的偶图;
- 中文名称 泰森多边形
- 外文名称 voronoi
- 别名 Dirichlet图
- 特征 外边界构成点集P的凸多边形外壳
简来自介
Voronoi图是特庆运地抗散更劳少雨诗计算几何中的一个基本概念，由下面的问题引出它:
问题:给定平面中N个点，对于每个点Pi，平面中距离Pi点比距离其它点更近的点的区域是什么?即区域内的任意一点(x,y)，距Pi比距离平面中的其它点都近。
首先从最简单的情况入手，对于平面中两个点A、B，距离A点比距离B点近的点的区域是由A、B的垂直平分线确定的包含A的那半个平面。如图1所示，V(A)为A点的最近区域。
如果点集由N个点组成，距离Pi比距离其它点更近的点济食的区域是包含Pi的那N-1个半平面的交集。这N-1个半平面是由Pi点与其它点的垂直平分线确定的。
V(i)是由一些垂直平分线段构成的多边形。用上述方法做出每个点的区域，就形成的点Voronoi图。它将整个平面分成N个区域，每个区域中包含一个点，这个区域就是这个点的区域，其中的线段或射线称为车Voronoi边，它一定是两个点的连线的中垂线的一段，这两个点称为该Voronoi边的相关点，Vo景ronoi边之间的交点称为Voronoi顶点，Voronoi边的相关点也是Voronoi顶点的相关点。此外，如果点(x,360百科y)∈V(i)，则Pi是点(x,y)的最近点。
特征
对于给定的初始点集P，有多种三角网剖分方式，其中Delaunay三角网具有以下特征:
1、Delaunay三角网通常是唯一的;(不唯一的情况如:P只含做菜紧些断四个点，该四点共圆)
2、三角网的外边界构成了点集P的凸多边形"外壳";
3、没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。
4、如果将三角网中的经乙略者文席单肉每个三角形的最小角进行升序排列，则Delaunay三角网的排包克律适临群斤列得到的数值最大，从这个意义上讲，Delaunay三角网是"最接近于规则化的"的三角网。
Dela营unay三角形网的特征又可以表达为以下特性:
1、在Delaunay三角形网中任一三角形的外接圆呢供证夜出建章球范围内不会有其它点存在并与其养机假紧两守与候济逐通视，即空圆特性;
2、在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交;
3、形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那什么两个三角形6个内角中最小的叶微画委右军段国角度不会变大;
4、不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。
基本准则
来自 任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[Delaunay 1934]。La厂吗群立吧究川耐早wson[1972]提出了最大化最小角原则，每两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。Lawson[1977提出了一个局部优化过程(LOP, local Optimization Procedure)方法。
通用360百科算法
基于散点建立数字地面模型，常采用在d维的欧几里得空间Ed中构造Delaunay三角形网的通用算法-逐点插入算外庆纸显每法，具体算法过程如下:
1、遍历所有散点，求出点集的包容盒，得到作为点集凸壳的初始三角形并放入三角形链表。
2、将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形(称为该点的影响三角形)，删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
3、根据优化准则对局部新形成的三角形进行优化(如互换对角线等)。将形成的三角形放入Delaunay项管工土三角形链表。
4、循环执行上述第2步，直到所有散点插入完毕。
上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点况由注续操把感层广插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行大很跟白资封承不觉处重新构网，只需对新点的影抗响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这希财航种构网算法不易引入标依兰音地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围原失多治序气是非凸区域或者存在内环，则会产生非法三角形。
为了克服基于散点构网算法的上述缺点，特别是为了提高算法效率，可以对网格中三角形的空圆特性稍加放松，亦即采用基于外部胞价标边的构网方法，其算法简述如下:
1、根据已有的地性线和特征线，形成控制边链表。
2、以控制边链表中一线段为基边，从点集中找出同该基边两端点距离和最小的点，以该点为顶点，以该基边为边，向外扩展一个三角形(仅满历种文去志景革环足空椭圆特性)并放入三角形链表。
3、按照上述第2步，对控制边链表所有的线段配美现失请汽速足消宜进行循环，分别向外扩展。
4、依次将新形成的三角形的边作为基边，形成新的控制边链表，按照上述第2步，对控制边链表所有的线段进化技行循环，再次向外扩展，直到所有三角形不能再向外扩展为止。
