Delaunay三角剖分算法

⑴ 闭合多边形的三角剖分算法

当剖面位于边界时，为了建立完整三维表面模型，需要对地层最小多边形(即闭合多边形)本身进行三角剖分，以便进行地层的缝合，构成一个闭合的三维地层表面模型。除了做约束Delaunay三角剖分之外，采用凸出点删除法(Øyvind et al.，2006)直接进行二维闭合多边形的三角剖分，从而避免Delaunay方法中还需将多边形进行垂直方向与水平方向来回的转换过程。

点p_i为闭合简单多边形C(P)上的有序点列之一，如果满足如下两个条件，则称p_i为凸出点，如图4.19a所示。

(1)相邻三节点p_i、p_i-1和p_i+1，满足∠p_i-1p_ip_i+1＜π；

(2)三角形T_i-1，i，i+1不包含p_i、p_i-1和p_i+1之外的点。

凸出点删除方法如下：

(1)查找多边形C(P)任意一个凸出点p_i。

(2)连接点p_i-1和p_i+1，创建三角形T_{i-1，i，i+1}，并将其存入三角形链表。然后，在多边形C(P)的点链表中删除点p_i。

(3)如果C(P)只剩三个点，则构成最后一个三角形；停止查找。

(4)回到(1)。

图4.19 闭合多边形三角剖分凸出点删除法过程

该方法所得到的多边形三角剖分结果不唯一。

局部优化方法：删除当前凸出点p_i后，优先判断点p_i-1和p_i+1是否为凸出点，若只有其中一个为凸出点，则将其作为当前凸出的点；若两个点都为凸出点，则选择角度最接近60°的凸出点。图4.19显示了一个闭合多边形三角化的整个过程。

⑵ 　Delaunay剖分及其性质

在二维情况下的三角网格和在三维情况下的四面体网格，具有很强的表示模型的能力。Delaunay剖分是二维Delaunay三角形化和三维Delaunay四面体化的总称。在二维情况下，指的是将一些随机散乱的点，连成三角形网，并给出每个三角形的相邻信息。首先，需要定义一个数据结构，使得三角形的组成及其相邻关系均可以用这个数据结构表示出来。

在二维情况下，这个数据结构通常用一个n×6维的矩阵表示出来。如图2.1（b）是一个三角形网，图2.1（c）是其三角形构成和相邻关系。这个矩阵的头三列为三角形结点的编号，后三列为相邻三角形的编号。

图2.1二维Delaunay剖分数据结构

（a）Dirichlet多边形；（b）Delaunay三角形化；（c）数据结构

如图，1号三角形是由15、5、4号点组成，其中15号点对边的相邻三角形编号4,5号点对边的三角形编号为2,4号点对边的三角形编号为0（指外边）。可见，当三角形的三个顶点的顺序在数据结构中确定下来以后，其相邻三角形编号的顺序和在数据结构中的位置也就确定下来了。在下面的所有Delaunay剖分算法，均是针对这一数据结构进行的。

给定一系列离散点坐标，所形成的三角形网并不是惟一的。目前应用最广泛的是Delaunay三角形化方法。

Delaunay三角形的定义应从Dirichlet多边形说起。在每个网格点附近划出一个邻域；邻域内的任一点到该网格点的距离小于到其他网格点的距离。这个邻域多边形称为Dirichlet多边形（图2.1（a）。将每个多边形内的格点与相邻的多边形的网格点连接起来，构成一个三角形，称为Delaunay三角形（图2.1（b））。Delaunay三角形具有一种性质，它可以尽可能的避免形成过瘦的三角形，因而在有限元计算中非常有用，因为有限元法的稳定性是由所有三角形的最小内角确定的。过瘦的三角形不利于射线追踪，因为它使得射线追踪经过的交点过多，从而会增加积累误差，增大计算量。Delaunay三角形的三角形数目大约为点的两倍。在三维情况下，Delaunay四面体的数目大约为点的7倍。文献（闵卫东、唐泽圣，1993）曾给出大量Delaunay三角形和四面体的点线、面的数量关系。

⑶ 带权限定Delaunay三角化的算法步骤及实现

1.二维的算法步骤及实现

带权的限定Delaunay三角剖分（Weighted CDT）的算法的输入是一个包含限定线段和限定点的平面直线图（planar straight line graph，简称PSLG），算法的输出是与限定条件（限定点和限定线段）一致的一个三角形集合。

算法4.7二维的带权限定Delaunay三角剖分

（PSLG）

{

规范化算法

调用算法WeightAssignment2d对PSLG中的点赋权值

建立初始大三角形

调用二维带权Delaunay空洞算法（算法4.2）生成受限点集的带权Delaunay三角剖分；

调用二维恢复受限边的算法（算法4.5）生成边界一致的带权Delaunay三角网格

删除边界外的多余的三角形，得到边界一致的带权限定Delaunay三角剖分

}

2.三维的算法步骤及实现

加权的限定Delaunay剖分的算法步骤：

输入：一个分段线性复合形（a piecewise linear complex）

输出：满足受限条件的具有带权Delaunay性质的四面体集合

算法三维的带权限定Delaunay四面体剖分算法：

（PLC）

{

调用算法4.4 WeightAssignment3d对规范化后的点和边赋权值；

建立初始大四面体

for所有的PLC中的平面

将该平面通过坐标变换转换到XOY平面上；

调用算法进行二维的带权限定Delaunay三角剖分

将得到的二维带权限定Delaunay三角网格坐标变换到空间中其原来位置

endfor

调用算法三维带权Delaunay空洞算法生成三维点集的带权Delaunay四面体剖分

调用算法RecoverConformSegments和算法RecoverConformFacets恢复受限边和受限面

删除边界外的多余的四面体，得到边界一致的带权限定Delaunay四面体剖分

}

⑷ 　快速Delaunay剖分

在Delaunay剖分算法中，2.2、2.3中（3）—（5）的计算量是一定的。而第一步，即找到所有待改三角形或四面体的过程，要消耗大量时间。为了使Delaunay剖分适应于快速人机交互处理，必须对其进一步优化。目前对三角形搜索的加速方法主要包含两种方法。

（1）定向搜索方法

在已形成的三角形数据结构中搜索需要N/2次搜索，但如果考虑定向搜索，则可以将搜索次数降到N^0.5（N为已形成三角形的数目）。方法如下。

判断新加入的点与三角形（图2.2中V₁）三边构成的面积，如果三个面积均为正，则加入点在三角形内，如果有至少一个为负（图2.2中P₃—P₂边），则该点位于为负的边的外侧。因此，可以进一步检查该边之相邻三角形（图2.2中V₂）。由此下去总能找到包含此新加入点的三角形。从这个包含新加入点的三角形出发，通过其相邻三角形搜索，便可以找到所有待修改的三角形。

图2.2定向搜索包含新加入点P之三角形

（2）树状存储法

在Delaunay剖分中，如果将所有以前的剖分结果记录下来，则可以找到一个树形结构，使每个三角形被新的三角形细分后，该三角形的信息仍能记录下来。这样就可以由一个初始的大三角形出发，每次只查找其内所含的三角形，三角形的面积迅速缩小，最后找到所属的小三角形，从而大大减少搜索时间。这种从大三角形到小三角形的搜索方法，计算量可以小于lgN，其代价是存贮量加大。

⑸ 区域的Delaunay三角剖分

从上文中介绍的对点集的Delaunay三角剖分方法可以知道，点集的Delaunay的三角剖分方法是最简单、最基础的，所以，可以考虑在点集的Delaunay三角剖分方法的基础上获得区域的Delaunay三角剖分，实际上，区域的Delaunay三角剖分方法正是这样做的。

为了利用点集的Delaunay三角剖分方法，首先应该将剖分对象从区域转换到点集，而为了实现上述目的，需要经过两个过程:布点、离散边界。布点即是向区域内插入一些合适的点，离散边界即是将区域边界分割成若干小线段。在进行上述处理后，就将需要剖分的对象从一个区域转变成一个点集，点集中的点为向区域内插入的点和边界离散后形成小线段的端点;然后采用点集的Delaunay三角剖分方法，如Lawson算法或Bowyer-Wat-son算法，对从区域转换过来的点集进行Delaunay三角剖分操作;最后需要删除那些在区域之外的三角形，因为对一个点集进行Delaunay三角剖分操作，最后获得的三角剖分的范围是该点集的凸壳，而点集的凸壳绝大多数情况下与需要剖分的区域不一致，通常情况下是凸壳的范围大于需要剖分的区域，因此那些属于凸壳但不属于需要剖分的区域的三角形需要删除。

区域的Delaunay三角剖分方法可以概括为3个步骤:

第一步:布点并离散边界，将剖分对象从区域转换为点集。根据剖分规模或想要得到的三角形单元的大概边长，向区域内插入一系列的内部点，并将内外边界离散成一系列的小线段。图3.14(a)为某剖分区域，图3.14(b)为向区域内布点的结果，图3.14(c)则时在布点之后进行离散边界的结果。

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

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

⑹ Delaunay三角剖分算法的准则特性

准则:
要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：
2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：

特性:
以下是Delaunay剖分所具备的优异特性：
1.最接近：以最近的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。

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

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

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;

⑻ 最优三角剖分的“最优”指的是什么最优

最优三角剖分的“最优”指的是应该是内角最接近最优。

定义一个t[i][j]，1<=i<=j<=N,为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。
Delaunay三角剖分算法指的是点集的三角剖分(Triangulation)，对数值分析(比如有限元分析)以及图形学来说，都是极为重要的一项预处理技术。尤其是Delaunay三角剖分，由于其独特性，关于点集的很多种几何图都和Delaunay三角剖分相关，如Voronoi图，EMST树，Gabriel图等。Delaunay三角剖分有最大化最小角，“最接近于规则化的“的三角网和唯一性(任意四点不能共圆)两个特点。

⑼ 点集的Delaunay三角剖分方法

3.2.1.1 基本理论

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

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

3.2.1.1.1 Voronoi图

假设V={v₁，v₂，…，v_N}，N≥3是欧几里得平面上的一个点集，并且这些点不共线，四点不共圆。用d(v_i，v_j)表示点v_i与v_j间的欧几里得距离。

设x为平面上的点，则:

区域V_(i)={x∈E²d(x，v_i)≤d(x，v_j)，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 Procere，LOP)优化使其满足Delau-nay三角网的要求，其主要步骤如下:

图3.7 Bowyer-Watson算法剖分实例

⑽ 　约束Delaunay剖分

约束Delaunay剖分就是强迫点按所需的连线进行连接。这种方法在构制含断层的曲面时非常有用。由于构造面上有断层存在，断层内是不需要连接线的，连接线必须含所需的线段。在这种情况下，就要用到约束Delaunay剖分。

Cline和Renka（1990）提出一种约束Delaunay剖分方法，这种方法首先将点按无约束Delaunay方法进行剖分。然后将所需的边加进去，形成对这种结构进行描述的数据矩阵。

约束Delaunay剖分的定义如下：一个三角形的外接圆内可以包含另一个结点，仅当该结点与该三角形被所需的连接边隔开的时候。

实际计算时，有如下算法：

（1）找到所有与要求的连接线相矛盾的三角形，将其中的内边去掉，构成一个多边形；

（2）将所要求的连接线加入到该多边形内；

（3）按照所对的顶点内角最大的原则，继续形成剩余的三角形边。

图2.3～图2.6给出了约束Delaunay剖分用于含断层构造面的三角形化的例子。

图2.3无约束Delaunay剖分（虚线为断层线）

图2.4约束Delaunay剖分（虚线）与无约束Delaunay剖分（实线）的比较

图2.5约束Delaunay剖分后挖去的断层

图2.6约束Delaunay剖分用于含断层的网络