谁对opencv里面的delaunay三角剖分方法比较熟悉的

点集的Delaunay三角剖分方法~

3.2.1.1 基本理论
B.Delaunay于1934年提出了Delaunay三角网格的概念，它是Voronoi图(简称V图)的几何对偶图，具有严格的数学定义和完备的理论基础。

图3.1 Voronoi图(虚线)及对应的Delaunay三角剖分(实线)

3.2.1.1.1 Voronoi图
假设V={v1，v2，…，vN}，N≥3是欧几里得平面上的一个点集，并且这些点不共线，四点不共圆。用d(vi，vj)表示点vi与vj间的欧几里得距离。
设x为平面上的点，则:
区域V(i)={x∈E2d(x，vi)≤d(x，vj)，j=1，2，…，N，j≠i}称为Voronoi多边形，也称为该点的邻域。点集中所有点的Voronoi多边形组成Voronoi图，如图3.1所示。
平面上的Voronoi图可以看做是点集V中的每个点作为生长核，以相同的速率向外扩张，直到彼此相遇为止而在平面上形成的图形。除最外层的点形成开放的区域外，其余每个点都形成一个凸多边形。
3.2.1.1.2 Delaunay三角剖分
Delaunay三角形网格为V图的几何对偶图。在二维平面中，点集中若无四点共圆，则该点集V图中每个顶点恰好是3个边的公共顶点，并且是3个Voronoi多边形的公共顶点;上述3个Voronoi多边形所对应的点集中的点连成的三角形称为与该Voronoi顶点对应的Delaunay三角形，如图3.1所示。如果一个二维点集中有四点共圆的情况，此时，这些点对应的Voronoi多边形共用一个Voronoi顶点，这个公共的Voronoi顶点对应多于3个Voronoi多边形，也就是对应于点集中多于3个的点;这些点可以连成多于一个的三角形。此时，可以任意将上述几个点形成的凸包划分为若干三角形，这些三角形也称为和这个Voronoi顶点对应的Delaunay三角形。
所有与Voronoi顶点对应的Delaunay三角形就构成了Delaunay三角剖分。当无退化情况(四点共圆)出现时，点集的Delaunay三角剖分是唯一的。
3.2.1.1.3 Delaunay三角剖分的特性
Delaunay三角剖分具有两个重要特性:
(1)最小角最大化特性:即要求三角形的最小内角尽量最大，具体地说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，6个内角的最小角不再增大，并且使三角形尽量接近等边。
(2)空外接圆特性:即三角形的外接圆中不包含其他三角形的顶点(任意四点不能共圆)，该特性保证了最邻近的点构成三角形，使三角形的边长之和尽量最小。
3.2.1.2 常用算法
Delaunay三角剖分方法是目前最流行的通用的全自动网格生成方法之一。比较有效的Delaunay三角剖分算法有分治算法、逐点插入法和三角网生长法等(Tsai，1993)，其中逐点插入法由于其算法的简洁性且易于实现，因而获得广泛的应用。其主要思路是先构建一个包含点集或区域的初始网格，再依次向初始网格中插入点，最后形成Delaunay三角剖分。
采用逐点插入法建立Delaunay三角网的算法思想最初是由Lawson于1977年提出的(Lawson，1977)，Bowyer和Watson等先后对该算法进行了发展和完善(Bowyer，1981;Watson，1981)。目前涌现出的大量逐点插入法中，主要为以Lawson算法代表的对角线交换算法和以Bowyer-Watson算法代表的空外接圆法。
3.2.1.2.1 Lawson算法
Lawson算法的主要思想是将要插入的数据点逐一插入到一个已存在的Delaunay三角网内，然后再用局部优化算法(Local Optimization Procedure，LOP)优化使其满足Delau-nay三角网的要求，其主要步骤如下:

图3.2 包含点集的三角形

第一步:构建一个三角形或多个三角形(通常情况下为一个三角形，该三角形也称超级三角形)，使点集中所有点都落在该三角形内，如图3.2所示。另外，也可以用一个矩形包围所有点，再将矩形对角线相连生成一对三角形作为初始网格。
第二步:将包含点集的三角形作为第一个三角形单元加入初始三角形网格中。
第三步:依次插入一个点P，并在三角网中找出包含P的三角形T，此时存在3种情况:
(1)P在三角形T内部，即P不落在三角形T的边或顶点上，把P与T的3个顶点相连，生成3个新的三角形，将新生成的三角形加入三角网，删除三角形T，如图3.3(a)所示。
(2)P在三角形T的一条边上，但不在顶点上，把P与T的3个顶点中与P相对的顶点相连，生成两个新的三角形，将新生成的三角形加入三角网，删除三角形T，如图3.4(b)所示。
(3)P在三角形T顶点上，不需处理，进行下一步操作。实际上，若点集中不存在相互重合的点，则P落在三角形T顶点上这种情况不会发生。

图3.3 向三角形网格中插入点P

上一步处理中，直接将三角形的顶点与P相连生成新的三角形单元不一定满足Delau-nay三角剖分的要求，因此，需要采用LOP算法对局部三角形进行优化。该算法的主要操作是进行边交换使新生成的三角形单元及其相邻的单元满足空外接圆特性。这样一个重要的过程其实非常简单，它就是运用Delaunay三角剖分的空外接圆特性对由两个有共用边的三角形组成的四边形进行判断，如果其中一个三角形的外接圆包含第四个顶点，则将这个四边形的对角线交换，如图3.4所示，在交换对角线后两个新三角形都满足空外接圆特性。
当两个有共用边的三角形具有相同的外接圆时，即存在四点共圆情况，此时，按照空外接圆特性，可以交换对角线也可以不交换对角线，那么这时候就要按照最小角最大化特性进行处理。具体做法是，先计算不进行边交换前三角形对中的6个内角的最小值，再计算进行边交换后6个内角的最小值，判断边交换前、后最小角是否变大，若是，交换，否则，不交换。上述操作就是为了尽量满足最小角最大化特性。

图3.4 四点不共圆时的边交换


图3.5 点集的Delaunay三角网格

第四步:在所有点被插入之后，从网格中删除多余的三角形单元，最后得到的网格就是点集的Delaunay三角网格，如图3.5所示。
按照上述算法，编程环境为VC++，Lawson算法的代码如下，其中参数CSurf*surf表示网格平面，网格结点和单元分别存储在成员pNodes和pTrgls中。函数IsPointInTrian-gle(x，y，tx［0］，ty［0］，tx［1］，ty［1］，tx［2］，ty［2］)用于判断点(x，y)是否落在由三点(tx［0］，ty［0］)、(tx［1］，ty［1］)和(tx［2］，ty［2］)组成的三角形中;函数LOP(CTrgl*ta，CTrgl*tb)采用LOP方法优化三角形对ta和tb。

三维地质建模方法及程序实现


三维地质建模方法及程序实现


三维地质建模方法及程序实现

3.2.1.2.2 Bowyer-Watson算法
Bowyer-Watson算法也是一种先形成初始网格，再逐步插入数据点进行细化的算法。与Lawson算法不同的是，Bowyer-Watson算法插入点时需要判断网格中三角形单元的外接圆是否包含该结点，而不是判断该三角形单元本身是否包含该结点;另外一个区别是Bowyer-Watson算法在每次插入一个点之后不需要像Lawson算法那样用LOP算法优化三角网。
Bowyer-Watson算法的主要步骤如下:
第一步:建立一个包含整个点集的初始网格。通常情况下初始网格为一个三角形或由一个矩形连接对角线得到的一对三角形。
第二步:依次将数据点插入到最近更新后得到的网格中，形成新的网格并更新，分为三小步:
(1)插入一个新点 P 到现有的 Delaunay 三角网格中，如图 3.6(a)所示。
(2)寻找并删除所有外接圆包含 P 点的三角单元，形成一个 Delaunay 空腔。图3.6(a)中的阴影三角形为外接圆包含 P 点的三角单元; 图 3.6(b)所示为形成的一个Delaunay 空腔。
(3)连接 P 点和 Delaunay 空腔边界上所有各点，形成新的 Delaunay 三角网格，如图3.6(c)所示。

图3.6 向三角形网格中插入点

第三步:删除多余的三角形，即如果某个三角形中的某个结点不属于原始的点集，则删除该三角形;最后结果即为点集的Delaunay三角剖分网格。
按照上述算法，编程环境为VC++，Bowyer-Watson算法的完整代码如下，其中参数CSurf*surf表示网格平面，网格结点和单元分别存储在成员pNodes和pTrgls中。函数TriangleInCircle()的作用是判断点(xp，yp)是否落在由三点(x1，y1)、(x2，y2)和(x3，y3)组成的三角形的外接圆内。

三维地质建模方法及程序实现


三维地质建模方法及程序实现


三维地质建模方法及程序实现


三维地质建模方法及程序实现

采用上述算法和代码，对一个包含46个点的点集进行Delaunay剖分，图3.7(a)所示为输入的点集，得到拥有74个三角形单元的网格，如图3.7(b)所示。

图3.7 Bowyer-Watson算法剖分实例

理论剖结唯确定现唯情况说明算问题

具体什么不太懂，不过我收藏了一个以前别人讲这方面的东西，你看看，希望对你有帮助。

Delaunay三角网是俄国数学家B.Delaunay于1934年发现的。关于Delaunay三角网构建的研究有许多，但由于本课题具有数据量大的特征，不宜直接沿用已有构建方法，笔者针对本课题数据特征，研究获得了适应本课题，速度较快的构建方法。Delaunay三角网有一个特性，每个三角网形成的外接圆都不包含其他参考点。利用这一个性质，我们可以直接构成Delaunay三角网：
一、建立第一个三角形
1、判断用来建立TIN的总脚点数，小于3则报错退出。
2、第一点的选择：
链表的第一节点，命名为Pt1;
3、第二点的选择：
A.非Pt1点； B.距Pt1最近
命名为Pt2
4、第三点的选择
A.非Pt1，Pt2点；
B.与Pt1，Pt2点组成的三角形的外接圆内无其他节点；
C.与Pt1，Pt2组成的三角形中的角Pt1Pt3Pt2最大。
命名为Pt3
5、生成三边，加入边表
6、生成第一个三角形，组建三角形表
二、扩展TIN
1、从边表头取一边，要求：该边flag标志为假（只在一个三角形中）
2、从点链表中搜索一点，要求：
A、与边中的Pixel3在边的异侧；
B、该点与边组成的三角形的外接圆内无其他点
C、满足上面两条件的点中角Pt1Pt3Pt2最大的点为Pt3。
3、判断新生成的边，如果边表中没有，则加入边表尾，设定标志flag为假，如果有，则设定该边flag为真。
4、将生成的三角形假如三角形表
5、设定选中的边的标志flag为真
6、转至1，直至边表边的标志flag全部为真。

数据结构：
struct Pixel //脚点数据
{
double x,y,z,g;
bool flag;
};
struct List //数据链表
{
Pixel *pixel;
List *next;
};
struct Line //三角形边
{
Pixel *pixel1; //三角形边一端点
Pixel *pixel2; //三角形边另一端点
Pixel *pixel3; //三角形边所对顶点
bool flag;
};
struct Linelist //三角形边表
{
Line *line;
Linelist *next;
};
struct Triangle //三角形表
{
Line *line1;
Line *line2;
Line *line3;
Triangle *next;
};

以下是我程序中关于建网的部分：
// DelaunayTIN.cpp: implementation of the CDelaunayTIN class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Reconstruction.h"
#include "DelaunayTIN.h"

#include "MyMath.h"
#include <math.h>
#include "ListControl.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CDelaunayTIN::CDelaunayTIN()
{

}

CDelaunayTIN::~CDelaunayTIN()
{

}

/////////////////////////////////////////////////////////////////////////////
//函数名： CreateDelaunayTIN
//编写者： Polaris
//参考资料：
//功能： 用给定的数据链表数据，组建Delaunay不规则三角网
//输入参数：数据链表list;区域范围(XMin,YMin),(XMax,YMax)
//输出参数：不规则三角网首三角形地址
//备注：
/////////////////////////////////////////////////////////////////////////////
struct Triangle * CDelaunayTIN::CreateDelaunayTIN(List *list)
{
//组建第一个三角形
CMyMath MyMath;
CListControl ListControl;
struct List *node;
struct Pixel *pt1,*pt2,*pt3;
bool flag;
struct Triangle *TIN;
pt1=list->pixel;
pt2=list->next->pixel;
node=list->next->next;
while(node!=NULL)
{
if(MyMath.Calculate2PtDistanceIn3D
(pt1->x,pt1->y,pt1->z,node->pixel->x,node->pixel->y,node->pixel->z)
<MyMath.Calculate2PtDistanceIn3D
(pt1->x,pt1->y,pt1->z,pt2->x,pt2->y,pt2->z))
{
pt2=node->pixel;
}
node=node->next;
}
node=list->next;
pt3=NULL;
while(node!=NULL)
{
if(node->pixel==pt1 || node->pixel==pt2)
{
node=node->next;
continue;
}
if(pt3==NULL)
{
pt3=node->pixel;
}
else
{
if((pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,node->pixel->x,node->pixel->y),2)+pow(MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,node->pixel->x,node->pixel->y),2)-pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt2->x,pt2->y),2))/(2*MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,node->pixel->x,node->pixel->y)*MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,node->pixel->x,node->pixel->y))
<(pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt3->x,pt3->y),2)+pow(MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,pt3->x,pt3->y),2)-pow(MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt2->x,pt2->y),2))/(2*MyMath.Calculate2PtDistanceIn2D(pt1->x,pt1->y,pt3->x,pt3->y)*MyMath.Calculate2PtDistanceIn2D(pt2->x,pt2->y,pt3->x,pt3->y)))
{
pt3=node->pixel;
}
}
node=node->next;
}
//LineList
Linelist *linehead,*linenode,*linelast;
Line *ln1,*ln2,*ln3;
linenode=new Linelist;
linenode->line=new Line;
linenode->line->pixel1=pt1;

Delaunay三角剖分是1934年发明的将空间点连接为三角形，使得所有三角形中最小角最大的一个技术。
如果你熟悉计算机图形学，你便会知道Delaunay三角剖分是变现三维形状的基础。如果我们在三维空间渲染一个，我们可以通过这个物体的投影来建立二维视觉图，并用二维Delaunay三角剖分来分析识别该物体，或者将它与实物相比较。Delaunay剖分是连接计算机视觉与计算机图形学的桥梁。然而使用OpenCV实现三角剖分的不足之处就是OpenCV只实现了二维的Delaunay剖分。如果我们能够对三维点进行三角剖分，也就是说构成立体视觉，那么我们可以在三维的计算机图形和计算机视觉进行无缝的转换。然而二维三角剖分通常用于计算机视觉中标记空间目标的特征或运动场景跟踪，目标识别，或两个不同的摄像机的场景匹配（如图从立体图像中获得深度信息）。
详情见http://m.blog.csdn.net/article/details?id=45598769

---

大石桥市17152294967： opencv中的BFMatcher和FlannBasedMatcher的区别 - ？
豆卢秆艾克： Brute Force匹配和FLANN匹配是opencv二维特征点匹配常见的两种办法,分别对应BFMatcher和FlannBasedMatcher. 二者的区别: BFMatcher总是尝试所有可能的匹配,从而使得它总能够找到最佳匹配. FlannBasedMatcher中FLANN的含义...

大石桥市17152294967： opencv里面有很多CV - EVENT - LBUTTONDOWN这样大写的,这些是不是预先定义的宏?那么是不是这些宏除了表示 - ？
豆卢秆艾克： 是宏.看宏的名字 CV_ :这是Opencv的标志,表明这个宏不是windows宏,是opencv定义的. EVENT_ :表示是一个事件中要用的的 LBUTTONDOWN:left button down鼠标左按钮按下事件.

大石桥市17152294967： 怎么配置opencv python3.6.1 anaconda - ？
豆卢秆艾克： 电脑系统:win7 64位,(其他系统类似) 关于Anaconda3-4.4.0下配置OpenCV3.2.01.首先官网下载最新版本的Anaconda3-4.4.0(基于自己的电脑选择32位或64位),该版本已经支持最新的Python3.6;注意:安装过程中:1)安装路径可以改...

大石桥市17152294967： 在C++中调用那个函数可以实现将 帧频数据流转换为图片格式存储? - ？
豆卢秆艾克： 如果知道帧的数据格式的话,可以生成图像文件、写文件头、写数据部分;对视频的处理,一般用DirectShow和OpenCV,可以很方便的抓取视频帧,对帧处理、

大石桥市17152294967： linux下opencv里样例的使用 - ？
豆卢秆艾克： 印象里面有一个build_all.sh脚本执行一下就可以了,这个记不太清了..不过编译自己写的程序是gcc -o test.bin test.c `pkg-config --cflags -libs opencv`g++ -o test.bin test.c `pkg-co...

大石桥市17152294967： OPENCV中利用DirectShow打开摄像头的问题 - ？
豆卢秆艾克： 一般来说会报缺少qedit.h和dxtrans.h 前一个问题你需要安装dxsdk_feb2005_extras.exe,下载解压后,里面的include目录下就有qedit.h头文件,然后设置你的include路径将其包含进去即可.第二个问题,你需要安装August 2007 DirectX SDK.如...

大石桥市17152294967： OpenCV中对于cvRectangle中有个scale的作用是什么 - ？
豆卢秆艾克： Rectangle 绘制简单、指定粗细或者带填充的 矩形 void cvRectangle( CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8, int shift=0 ); img 图像. pt1 矩形的一个顶点. pt2 矩形对角线上的另一个顶点 color 线条颜...

大石桥市17152294967： opencv中CvFont font; cvInitFont(&font,CV - FONT - HERSHEY - SCRIPT - COMPLEX,1,1);对应于c++中的那些? - ？
豆卢秆艾克： 你的这些函数是字体的初始化函数吧,在c++中也有字体的库,字体由CFont类进行管理,创建CFont类必须使用CFont类的成员函数.CFont InfoFont; InfoFont.CreateFont();

大石桥市17152294967： OpenCV中的指针 - ？
豆卢秆艾克： 这个是结构体指针,这样可以通过指针来引用结构体类型变量.举个例子,比如最常见的IplImage*,如果定义了IplImage* img,那么就可以引用结构体的变量(具体变量看一下IplImage结构体),例如img->width就是图像的宽,img->height就是图像高等等.比如你的第一个CvMat结构体,按照你的定义可以引用M->rows矩阵行数,M->cols矩阵列数,rows和cols都是在CvMat结构体里面定义的.你查找下手册看看结构体是怎么定义的,里面的变量都可以通过这种方式引用. 至于你说的空格问题,两种写法是一样的.空格在前在后无所谓.

大石桥市17152294967： OPENCV里打开摄像头 为啥要用 if (argc ==1){………… return - 2} 之类的东西 求解释(比如下边的代码) - ？
豆卢秆艾克： argc == 1命令只有程序,没有输入文件,因此打开摄像头作为输入 argc == 2命令包含了输入文件,读取字符串argv[1]表示的文件作为输入