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细分

地质特征具有结构性(局部连续性)，而实际地质采样具有不规则性和稀疏性，使得由钻孔孔口坐标点所剖分的初始三角网格可能存在畸形和尺寸过大的情况，可视化效果差，也不能真实地反映地层的分布特征。因此，需要对初始三角网格进行细分，以消除这些影响。

网格细分要求进行质量控制和尺度控制(杨钦，2005)。质量控制方法是在畸形网格单元顶点附近加点的方法来实现。加点细化后网格保持了Delaunay三角化的一些优良特性，且向一个符合Delaunay优化准则的网格中加入一个点是一个局部运算，算法效率更高。主要采用两种加点方法：①畸形网格单元的最长边中点加点；②畸形网格单元的外接圆圆心加点。通常，第二种方法优于第一种方法。

为了使网格具有一定的密度，对于尺寸超过标准的网格单元应该进行加点细分。加点方案同质量控制一样。

因此，无论是对三角网进行质量控制还是尺寸控制，均选择三角单元外接圆圆心作为点插入的位置。同时，需要建立评价点插入的收敛准则：

(1)用三角形单元的外接圆半径与内切圆半径的比值来度量网格单元的质量，称为三角形单元的纵横比(aspect ratio)；

(2)用三角单元的外接圆半径与最短边长度的比值来度量网格单元的质量，建成为Radius-Edge比。用ρ来表示三角单元T的Radius-Edge比，R表示T的外接圆半径，L_min表示T的最短边长度，有：

数字地下空间与工程三维地质建模及应用研究

由于三角形的内切圆半径的计算比较烦琐，通常采用第二种方法作为三角形的质量评价标准。采用三角形的Radius-Edge比作为质量评价的另一个好处是根据三角形T的Radius-Edge比ρ(T)可以直接计算三角形最小角的角度，如图3.9所示。

图3.9 三角形的Radius-Edge比和最小角度的关系

由图3.9中的几何关系可以得到：

数字地下空间与工程三维地质建模及应用研究

不难看出，ρ(T)具有明显几何意义：

ρ(T)越大，T的最小角度也越小，T就越畸形。

ρ(T)越小，T的最小角度也越大，T就越接近正三角形。

当T是正三角形时，ρ(T)达到最小，其值为

，网格质量最好。

通过设置不同的网格质量和尺寸的控制性参数，可以得到不同的网格质量和密度的网格剖分结果，从而可以实现模型的精度控制。图3.10是以中国主要陆地区域作为约束边界，一些控制点作为约束点，在一定质量和尺寸控制下的三角剖分，剖分结果为非常均匀的三角网格。该方法用于钻孔加密，可以实现钻孔(包括虚拟钻孔)的相对均匀分布，进而可以了解各个位置处的地层分布。

❸ 　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三角剖分算法的准则特性

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

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

❺ 　三维Delaunay算法

将Delaunay剖分算法推广到三维具有重要意义。三维Delaunay剖分构成的Delaunay四面体是进一步构成任意块体的中间工具。三维空间的四面体对于三维射线追踪非常方便。三维Delaunay算法基本原理与二维Delaunay算法十分相似，但编制起来更为复杂。它也要用一个n×8维数组记录四面体构成点和相邻四面体信息，它大致也分为以下几步：

（1）判断哪些四面体的外接球包含新加入的点；

（2）将这些四面体汇总到一块，形成一个凸多面体；

（3）找到这多面体外表面，用一个二维三角形相邻关系数组记录下来；

（4）由多面体表面的三角形与新加入的点构制新四面体，用一个三维四面体数据结构数组，存贮新形成的四面体信息；

（5）用新四面体信息去更新原来总的四面体数据结构信息。

其中第（3）步是比二维Delaunay剖分复杂。待修改的四面体的外表面不再能够用环表示，而要用一个二维Delaunay三角形数据结构来表示。这种三角形的相邻关系要从原四面体的数据结构关系中去寻找。A、C面是多面体的外表面。B是其内表面须寻找A的一个棱的相邻三角形B，从B找到下一个四面体，再从四面体上找到与B三角形棱相邻的面C。

在三维Delaunay算法中，在通过外接球找到所有待修改的四面体后，将其排成一个待修改四面体数据结构数组，将待修改四面体的所有面全部排列起来，其中包含各个四面体的相互公共面和这些四面体组成的多面体的外表面，构成一个关于面的数据结构数组。从这个数据结构中删去相互相邻的三角形面，这样就构成了外表面的数据结构数组。

三维Delaunay剖分时，我们总利用三角形网格中的数量关系，来检查所形成的四面体的正确性。如果待删四面体数目为T，外表面三角形的数目为F，则

地质模型计算机辅助设计原理与应用

❻ Delaunay三角剖分算法的定义

【定义】三角剖分 ：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：
1.除了端点，平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。
在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
优化处理:
理论上为了构造Delaunay三角网 ，Lawson提出的局部优化过程LOP(Local Optimization Procere)，一般三角网经过LOP处理，即可确保成为Delaunay三角网，其基本做法如下所示：
1.将两个具有共同边的三角形合成一个多边形。
2.以最大空圆准则作检查，看其第四个顶点是否在三角形的外接圆之内。
3.如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。
LOP处理过程如下图所示：
Delaunay剖分的算法
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剖分的Bowyer算法

在实际计算中Delaunay剖分通常采用如下定义：在形成的每个三角形的外接圆内都不包含网格点。

据此，Lawson和Bowyer提出的Delaunay三角形化算法，是通过不断地增加网格点迭代计算的。算法分为如下几点：

（1）判断新加入的格点与三角形外接圆的内外关系，如果在某三角形外接圆内，则这个三角形需要改造。

（2）将所有需要改造的三角形集中起来，把它们的相邻边去掉，构成一个凸的多边形。

（3）找到这个多边形的外边界，并利用它们的相邻关系把它们连接起来构成一个头尾相接的环。

（4）将环上的每两个相邻的网格点取出，与待加入的网格点构造三角形，计算其外心，并将相邻三角形的信息建立起来，将三角形网格点和相邻三角形信息储贮在只包含这些三角形的Delaunay剖分的数据结构数组中。

（5）将上述新加入的三角形数据结构数组替换三角形数据结构数组中需要改造的三角形，并对三角形重新编号，从而得到新的结构数组。

❿ 空间点集的带权Delaunay三角化算法

构造点集的Delaunay三角化的着名增量算法有两种：一种称为局部变换法（也称为Flip-ping算法），另外一种称为Bowyer/Watson算法。构造空间点集的带权Delaunay三角化算法也主要有两种，分别是以上两种算法的推广。我们只介绍推广后的Bowyer/Watson算法，称之为“带权Delaunay空洞算法构造点集的带权Delaunay三角化”算法。

1.带权Delaunay空洞定义

给定Ed空间的点集S，设有一点p∉S位于点集S的凸包中。Δ=ΔT是点集S的带权Delaunay三角化中的任意一个单纯形，z=z（Δ）为Δ的正交中心。如果满足wp＞πz（p），则称为Δ和p点冲突（也可以将单纯形的正交中心理解为权为正交球半径平方的带权点，当该点与p点干涉时，单纯形和p点冲突）。在带权Delaunay三角化的结果中，将所有与p点冲突的单纯形从带权Delaunay三角化中删除，将形成一个空洞，称为带权Delaunay空洞，又称为Regular空洞（Regular Cavity）。

根据d维空间的带权Delaunay三角化与d+1维空间的凸包之间的关系，可以在d+1维空间的凸包CH（S+）上考察将p点加入带权Delaunay三角化中带权Delaunay空洞的形成过程：如果Δ=ΔT和p点冲突，意味着p+点在过ΔT+=CH（T+）的超平面的下方。在带权Delaunay三角化中，删除CH（S+）的所有p+在其下方的下部小面对应的单纯形，形成带权Delaunay空洞。

2.带权Delaunay空洞构造算法

带权Delaunay空洞构造算法的思路如下：带权Delaunay空洞构造算法是一种增量算法，S中的点是逐点加入、逐点处理的。与局部变换算法一样，需要选择一个初始的足够大的d-单纯形。设点集S={p1，p2，…，pn}，选择d+1的权为0的点构成点集S0={p-d，p-d+l，…，p0}，构造一个d-单纯形ΔS0=CH（S0）。选择的S0要保证ΔS0包含S中所有的点，并且保证WD（S）的每个d-单纯形是WD（S ∪ S0）的d-单纯形。

定义Si={p-d，p-d+1，…，pi}。给定R（Si-1），设Δ=ΔT是WD（Si-1）中包含pi点的d-单纯形。如果加入pi后，Δ仍然是正则的，则WD（Si）=WD（Si-1）。否则，删除Δ，并且根据邻接关系，删除Δ周围所有与pi冲突的d-单纯形，得到pi点的带权Delaunay空洞，并且将空洞多面体的每个小面的顶点和pi相连形成新的d-单纯形，从而得到WD（Si）。当点集S中所有的点处理完成后，将得到WD（S）。

算法：带权Delaunay空洞构造算法

{

1 构造WD（S0）=ΔS0

2 for i：=1 to n do

3 在WD（Si-1）中找到包含pi点的d-单纯形Δ

4 if WD（T ∪{pi}）≠ΔT then

删除Δ，并且根据邻接关系，删除Δ周围所有与pi冲突的d-单纯形，得到pi点的带权D elaunay空洞

6 while pi点的带权Delaunay空洞中存在未处理的小面do

7 得到一个未处理的小面，设其所有顶点组成的集合为U，生成新的d-单纯形ΔU ∪{pi}，在点集Si中是正则的，也就是说Δ属于W D（Si）设置新生成的d-单纯形之间的邻接关系，以及新的

地下水三维可视化系统开发与应用