voronoi图

凸组合

凸组合是一类特殊的线性组合。

凸组合(convex combination)：[1] 如图，点P是在平面图中所示的三点x1、x2、x3的凸组合，而Q则不是。

凸集

在凸几何中，凸集(convex set)是在凸组合下闭合的仿射空间的子集。更具体地说，在欧氏空间中，凸集是对于集合内的每一对点，连接该对点的直线段上的每个点也在该集合内。例如，立方体是凸集，但是任何中空的或具有凹痕的例如月牙形都不是凸集。

特别的，凸集，实数R上（或复数C上）的向量空间中，如果集合S中任两点的连线上的点都在S内，则称集合S为凸集。

凸包

⒈对于一个集合D，D中任意有限个点的凸组合的全体称为D的凸包。
⒉对于一个集合D，所有包含D的凸集之交称为D的凸包。
可以证明，上述两种定义是等价的。

概念

1. 点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

2. 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。计算几何里的一种基于距离的平面划分方法。在平面上有n个不重合种子点，把平面分为n个区域，使得每个区域内的点到它所在区域的种子点的距离比到其它区域种子点的距离近。每个区域称为该种子点的Voronoi区域。Voronoi图是Delaunay三角剖分的对偶图。Voronoi图的每条边是由相邻种子点的垂直平分线构成，在边上的点到两个种子点的距离相等。

Delaunay三角剖分算法

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

1. 除了端点，平面图中的边不包含点集中的任何点。
2. 没有相交边。
3. 平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。

在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：

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

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

自己的理解：其实这一段过程就是为了得到像上图一样的三角形网络（网络中的边不相交）。得到这种网络的方法有很多，但是，用外接圆的方式得到这种三角形网络较为简单。

优化处理:

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

1. 将两个具有共同边的三角形合成一个多边形。
2. 以最大空圆准则作检查，看其第四个顶点是否在三角形的外接圆之内。
3. 如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。

LOP处理过程如下图所示：

Delaunay三角剖分法：https://baike.baidu.com/item/Delaunay%E4%B8%89%E8%A7%92%E5%89%96%E5%88%86%E7%AE%97%E6%B3%95/3779918?fr=aladdin

voronoi图

计算几何里的一种基于距离的平面划分方法。在平面上有n个不重合种子点，把平面分为n个区域，使得每个区域内的点到它所在区域的种子点的距离比到其它区域种子点的距离近。每个区域称为该种子点的Voronoi区域。Voronoi图是Delaunay三角剖分的对偶图。Voronoi图的每条边是由相邻种子点的垂直平分线构成，在边上的点到两个种子点的距离相等。

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

构造方法

Voronoi图是Delaunay三角剖分的对偶图，生成它的方法有很多[2] ，比较有名的有分治算法，扫描线算法，增量法等。但利用Delaunay三角剖分生成Voronoi图的算法是最快的。

但最快的方法则是构造Delaunay三角剖分，再连接相邻三角形的外接圆圆心，即可以到Voronoi图。

Delaunay三角剖分算法：

1. Delaunay三角网是唯一的；

2. 三角网的外边界构成了点集P的凸多边形“外壳”；

3. 没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。

4. 如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。

Delaunay三角形网的特征又可以表达为以下特性：

1. 在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；

2. 在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；

3. 形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；

4. 不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。

Delaunay三角形产生的基本准则：

任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[Delaunay 1934]。Lawson[1972]提出了最大化最小角原则，每两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。Lawson[1977提出了一个局部优化过程（LOP, local Optimization Procedure）方法。

基于散点建立数字地面模型，常采用在d维的欧几里得空间Ed中构造Delaunay三角形网的通用算法—逐点插入算法，Delaunay三角剖分算法过程如下：

1. 遍历所有散点，求出点集的包容盒，得到作为点集凸壳的初始三角形并放入三角形链表。

2. 将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。

3. 根据优化准则对局部新形成的三角形进行优化（如互换对角线等）。将形成的三角形放入Delaunay三角形链表。

4. 循环执行上述第2步，直到所有散点插入完毕。

上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法不易引入地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。

为了克服基于散点构网算法的上述缺点，特别是为了提高算法效率，可以对网格中三角形的空圆特性稍加放松，亦即采用基于边的构网方法，其算法简述如下：

1. 根据已有的地性线和特征线，形成控制边链表。

2. 以控制边链表中一线段为基边，从点集中找出同该基边两端点距离和最小的点，以该点为顶点，以该基边为边，向外扩展一个三角形（仅满足空椭圆特性）并放入三角形链表。

3. 按照上述第2步，对控制边链表所有的线段进行循环，分别向外扩展。

4. 依次将新形成的三角形的边作为基边，形成新的控制边链表，按照上述第2步，对控制边链表所有的线段进行循环，再次向外扩展，直到所有三角形不能再向外扩展为止。