点集的Delaunay三角剖分方法

Answer 1

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 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()的作用是判断点(x_p，y_p)是否落在由三点(x₁，y₁)、(x₂，y₂)和(x₃，y₃)组成的三角形的外接圆内。

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

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

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

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

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

图3.7 Bowyer-Watson算法剖分实例