OpenCV——Delaunay三⾓剖分（C++实现）
最近做三⾓剖分发现了⼀篇很好的博客，其中的代码都可以实现，特在此分享给⼤家，希望可以⼀起学习，有问题共同探讨。
------------------
--------------------------------------------------------
Delaunay三⾓剖分是1934年发明的将空间点连接为三⾓形，使得所有三⾓形中最⼩⾓最⼤的⼀个技术。
如果你熟悉计算机图形学，你便会知道Delaunay三⾓剖分是变现三维形状的基础。如果我们在三维空间渲染⼀个，我们可以通过这个物体的投影来建⽴⼆维视觉图，并⽤⼆维Delaunay三⾓剖分来分析识别该物体，或者将它与实物相⽐较。Delaunay剖分是连接计算机视觉与计算机图形学的桥梁。然⽽使⽤OpenCV实现三⾓剖分的不⾜之处就是OpenCV只实现了⼆维的Delaunay剖分。如果我们能够对三维点进⾏三⾓剖分，也就是说构成⽴体视觉，那么我们可以在三维的计算机图形和计算机视觉进⾏⽆缝的转换。然⽽⼆维三⾓剖分通常⽤于计算机视觉中标记空间⽬标的特征或运动场景跟踪，⽬标识别，或两个不同的摄像机的场景匹配（如图从⽴体图像中获得深度信息）。
1、三⾓剖分与Delaunay剖分的定义
如何把⼀个离散⼏何剖分成不均匀的三⾓形⽹格，这就是离散点的三⾓剖分问题，散点集的三⾓剖分，对数值分析以及图形学来说，都是极为重要的⼀项处理技术。该问题图⽰如下：
1.1 三⾓剖分定义
【定义】三⾓剖分：假设V是⼆维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段，E为e的集合。那么该点集V的⼀个三⾓剖分T=(V,E)是⼀个平⾯图G，该平⾯图满⾜条件：
1、除了端点，平⾯图中的边不包含点集中的任何点。
2、没有相交边。（边和边没有交叉点）
3、平⾯图中所有的⾯都是三⾓⾯，且所有三⾓⾯的合集是散点集V的凸包。
1.2 Delaunay三⾓剖分的定义
在实际中运⽤的最多的三⾓剖分是Delaunay三⾓剖分，它是⼀种特殊的三⾓剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的⼀条边e(两个端点为a,b)，e若满⾜下列条件，则称之为Delaunay边：存在⼀个圆经过a,b亮点，圆内（注意是园内，圆上最多三点共圆）不含点集V中任何其他的点，这⼀特性⼜称空圆特性。
【定义】Delaunay三⾓剖分：如果点集V的⼀个三⾓剖分T只包含Delaunay边，那么该三⾓剖分称为Delaunay三⾓剖分。
1.3 Delaunay三⾓剖分的准则
要满⾜Delaunay三⾓剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三⾓⽹是唯⼀的（任意四点不能共圆），在Delaunay三⾓形⽹中任⼀三⾓形的外接圆范围内不会有其它点存在。如下图所⽰：
2、最⼤化最⼩⾓特性：在散点集可能形成的三⾓剖分中，Delaunay三⾓剖分所形成的三⾓形的最⼩⾓最⼤。从这个意义上讲，Delaunay三⾓⽹是“最接近于规则化的”三⾓⽹。具体的说是在两个相邻的三⾓形构成凸四边形的对⾓线，在相互交换后，两个内⾓的最⼩⾓不再增⼤。如下图所⽰：
1.4 Delaunay三⾓剖分的特性
以下是Delaunay剖分所具备的优异特性：
1、最接近：以最接近的三点形成三⾓形，且各线段（三⾓⾏的边）皆不相交。
2、唯⼀性：不论从区域何处开始构建，最终都将得到⼀致的结果。
3、最优性：任意两个相邻三⾓形构成的凸四边形的对⾓线如何可以互换的话，那么两个三⾓形六个内⾓中最⼩⾓度不会变化。
the frozen ground
4、最规则：如果将三⾓⽹中的每个三⾓形的最⼩⾓进⾏升序排列，则Delaunay三⾓⽹的排列得到的数值最⼤。
5、区域性：新增、删除、移动某⼀个顶点只会影响邻近的三⾓形。
6、具有凸边形的外壳：三⾓⽹最外层的边界形成⼀个凸多边形的外壳。
1.5局部最优化处理
vitaminx理论上为了构造Delaunay三⾓⽹，Lawson提出的局部优化过程LOP(Local Optimization Procedure),⼀般三⾓⽹经过LOP处理，即可确保为Delaunay三⾓⽹，其基本做法如下所⽰：
1、将两个具有共同边的三⾓形合成⼀个多边形。
2、以最⼤空圆准则作检查，看其第四个顶点是否在三⾓形的外接圆内。
3、如果在，修正对⾓线即将对⾓线对调，即完成局部优化过程的处理。
LOP处理过程如下图所⽰：
2、Delaunay剖分的算法
Delaunay剖分是⼀种三⾓剖分的标准，实现它有多种算法。
由表可以看出，三⾓⽹⽣成法的时间效率最低，分治算法的时间效率最⾼，逐点插⼊法效率居中。由于区域⽣长法本质的缺陷，导致其效率受限，这种⽅法在80年代中期以后已经很少使⽤。分治算法时间效率相对较⾼，但是由于其递归执⾏，所以需要较⼤的内存空间，导致其空间效率较低。此外，分治法的数据处理及结果的优化需要的⼯作量也⽐较⼤。逐点插⼊算法实现简单，时间效率⽐较⾼，⽽运⾏占⽤的空间也较⼩，从时间效率和空间效率综合考虑，性价⽐最⾼，因⽽应⽤⼴泛。
1977年，Lawson提出了逐点插⼊法建⽴Delaunay三⾓⽹的算法思想。之后Lee和Schachlter,Bowyer,Watson,Sloan，先后进⾏了发展和完善。他们的算法在初始化三⾓⽹的建⽴⽅法、定位点所在三⾓形的过程、以及插⼊的过程⽅⾯各具特点。
2.1 Lawson算法
逐点插⼊的Lawson算法是Lawson在1977提出的，该算法思路简单，易于编程实现。基本原理为：⾸先建⽴⼀个⼤的三⾓形或多边形，把所有数据点包围起来，向其中插⼊⼀点，该点与包含它的三⾓形三个顶点相连，形成三个新的三⾓形，然后逐个对它们进⾏空外接圆检测，同时⽤Lawson设计的局部最优化过程LOP进⾏优化，集通过交换对⾓线的⽅法来保证所形成的三⾓⽹为Delaunay三⾓⽹。
上述基于散点的构⽹算法理论严密、唯⼀性好，⽹格满⾜空圆特性，较为理想。由其逐点插⼊的构⽹过程可知，遇到⾮Delaunay边时，通过删除调整，可以构造形成新的Delaunay边。在完成构⽹后，增
高一英语必修一加新点时，⽆需对所有点进⾏重新构⽹，只需要对新点的影响三⾓形范围进⾏局部联⽹，且局部联⽹的⽅法简单易⾏。同样，点的删除、移动也可快速动态地进⾏。但在实际应⽤当中，这种构⽹算法当点集较⼤时⽹速度也较慢，如果点集范围是⾮凸区域或者存在内环，则会产⽣⾮法三⾓形。
2.2 Bowyer-Watson算法
⽬前采⽤逐点插⼊⽅式⽣成的Delaunay三⾓⽹的算法主要基于Bowyer-Watson算法，Bowyer-Watson算法的主要步骤如下：
1）建⽴初始三⾓⽹格：针对给定的点集V，找到⼀个包含该点集的矩形R，我们称R为辅助窗⼝。连接R的任意⼀条对⾓线，形成两个三⾓形，作为初始Delaunay三⾓⽹格。
2）逐点插⼊：假设⽬前已经有⼀个Delaunay三⾓⽹格T，现在在它⾥⾯再插⼊⼀个点P，需要找到该点P所在的三⾓形。从P所在的三⾓形开始，搜索该三⾓形的邻近三⾓形，并进⾏空外接圆检测。找到外接圆包含点P的所有的三⾓形并删除这些三⾓形，形成⼀个包含P的多边形空腔，我们称之为Delaunay空腔。然后连接P与Delaunay腔的每⼀个顶点，形成新的Delaunay三⾓⽹格。
大使馆英文3）删除辅助窗⼝R：重复步骤2），当点集V中所有点都已经插⼊到三⾓形⽹格中后，将顶点包含辅助窗⼝R的三⾓形全部删除。
在这些步骤中，快速定位点所在的三⾓形、确定点的影响并构建Delaunay腔的过程是每插⼊⼀个点都会进⾏的。随着点数的增加，三⾓形数⽬增加很快，因此缩短这两个过程的计算时间，是提⾼算法效率的关键。
算法执⾏图⽰如下：
、
cereal怎么读3、OpenCV中的Delaunay和Voronoi细分
学习这部分，也是⼀个头疼的问题，要理解需要较好的数据结构作为基础。由于⾃⼰对数据结构也是敬畏三分，所以下⾯理解不免有误。OpenCV中现实的Delaunay三⾓剖分应该是Bowyer-Watson算法。
3.1创建⼀个Delaunay或Voronoi细分。
我们需要存储Delaunay的内存空间和⼀个外接矩形（该矩形盒⼦⽤来确定虚拟三⾓形）
// STORAGE AND STRUCTURE FOR DELAUNAY SUBDIVISION //存储和结构 for三⾓剖分
//
roxaneCvRect rect = { 0, 0, 600, 600 }; //Our outer bounding box //我们的外接边界盒⼦
CvMemStorage* storage; //Storage for the Delaunay subdivsion //⽤来存储三⾓剖分
storage = cvCreateMemStorage(0); //Initialize the storage //初始化存储器
CvSubdiv2D* subdiv; //The subdivision itlf // 细分
subdiv = init_delaunay( storage, rect); //See this function below //函数返回CvSubdiv类型指针
init_delaunay函数如下，它是⼀个OpenCV函数，是⼀个包含⼀些OpenCV函数的函数包。
//INITIALIZATION CONVENIENCE FUNCTION FOR DELAUNAY SUBDIVISION //为三⾓剖分初始化便利函数
//
CvSubdiv2D* init_delaunay(CvMemStorage* storage,CvRect rect) {
CvSubdiv2D* subdiv;
subdiv = cvCreateSubdiv2D(CV_SEQ_KIND_SUBDIV2D,sizeof(*subdiv),sizeof(CvSubdiv2DPoint),sizeof(CvQuadEdge2D),storage);//为数据申请空间cvInitSubdivDelaunay2D( subdiv, rect ); //rect ts the bounds
return subdiv;//返回申请空间的指针
}
我们知道三⾓剖分是对散点集进⾏处理的，我们知道了散点集就可以获得点集的三⾓剖分。如何传⼊（插⼊）散点集呢？
这些点必须是32位浮点型，并通过下⾯的⽅式插⼊点：
CvPoint2D32f fp; //This is our point holder//这是我们点的持有者（容器）
for( i = 0; i < as_many_points_as_you_want; i++ ) {
// However you want to t points //如果我们的点集不是32位的，在这⾥我们将其转为CvPoint2D32f，如下两种⽅法。
//
fp = your_32f_point_list[i];
cvSubdivDelaunay2DInrt( subdiv, fp );
}
转换为CvPoint2D32f的两种⽅法：
1）通过宏cvPoint2D32f(double x,double y)
2）通过cxtype.h下的cvPointTo32f(CvPoint point)函数将整形点⽅便的转换为32位浮点型。
当可以通过输⼊点（散点集）得到Delaunay三⾓剖分后，接下来，我们⽤⼀下两个函数设置和清除相关的Voronoi划分：
view plaincopy在CODE上查看代码⽚派⽣到我的代码⽚
cvCalcSubdivVoronoi2D( subdiv ); // Fill out Voronoi data in subdiv //在subdiv中填充Vornoi的数据
cvClearSubdivVoronoi2D( subdiv ); // Clear the Voronoi from subdiv//从subdiv中清除Voronoi的数据
CvSubdiv2D结构如下：
#define CV_SUBDIV2D_FIELDS() \
CV_GRAPH_FIELDS() \em的用法
int quad_edges; \
int is_geometry_valid; \
CvSubdiv2DEdge recent_edge; \
CvPoint2D32f topleft; \
CvPoint2D32f bottomright;
during的用法typedef struct CvSubdiv2D
{
CV_SUBDIV2D_FIELDS()
}
CvSubdiv2D;
#define CV_GRAPH_FIELDS()
CV_SET_FIELDS() /* t of vertices */
CvSet *edges; /* t of edges */
#define CV_SET_FIELDS()
CV_SEQUENCE_FIELDS() /*inherits from [#CvSeq CvSeq] */easter day
struct CvSetElem* free_elems; /*list of free nodes */
平⾯划分是将⼀个平⾯分割为⼀组不重叠的、能够覆盖整个平⾯的区域。结构CvSubdiv2D描述了建⽴在⼆维点集上的划分结构，其中点集互相连接且构成平⾯图形，该图形通过结合⼀些⽆线连接外部划分点（称为凸形点）的边缘，将⼀个平⾯⽤按照其边缘划分成很多⼩区域。对于每⼀个划分操作，都有⼀个对偶划分与之对应。对偶的意思是⼩区域与点（划分的顶点）变换⾓⾊，即在对偶划分中，⼩区域被当做⼀个顶点（以下称为虚拟点）⽽原始的划分顶点被当做⼩区域。如下图所⽰，原始的划分⽤实线表⽰，⽽对偶划分⽤虚线表⽰。
汉译英工具
OpenCV使⽤Delaunay算法将平⾯分割成⼩的三⾓形区域（该三⾓形确保包括所有的分割点）开始不断迭代完成。在这种情况下，对偶划分就是输⼊的⼆维点集的Voronoi图表。这种划分可以⽤于对⼀个平⾯进⾏三维分段变换、形态变换、平⾯点的快速定位以及建⽴特定的图结构（如NNG,RNG）。
CvQuadEdge2D
CvQuadEdge2D结构包含了两个Delaunay点和两个Vorionoi点以及连接它们的边缘（假设Voronoi点和边缘已经由函数计算出来，通过上⾯的函数：cvCalSubdivVoronoi2D(subdiv)）。
CvQuadEdge2D定义平⾯划分中的Quad-edge（四⽅边缘结构），其结构如下：
