区域的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)则时在布点之后进行离散边界的结果。

图3.14 二维区域布点与边界离散

第二步:对点集进行Delaunay三角剖分操作。将离散后的内外边界的端点和根据需要布设的内部点组成输入点集，采用逐点插入法(Lawson算法或Bowyer-Watson算法)将上述点集进行Delaunay三角剖分，详细步骤请参见本章中点集的Delauany三角剖分方法，最后点集的Delaunay三角剖分如图3.15所示。剖分区域之外的三角形只能是由同一条边界上线段的端点组成，不可能由内部点或不同边界(如2个顶点位于外边界，1个顶点位于内边界)上端点组成区域之外的三角形，所以，判断一个三角形是否多余，首先判断该三角形的3个点是否位于同一条边界，若是，该三角形有可能为多余三角形，但不一定，如图3.16中由点9、10和11组成的三角形位于区域内部，但由点21、22和23组成的三角形却在区域外;因此，三角形的3个顶点位于同一条边界上只是必要条件，还需要进一步判断。

图3.15 点集的Delaunay三角剖分(未进行边界处理)

第三步:边界处理。根据区域边界，删除多余的三角形，得到区域的Delaunay三角剖分。

完整的边界处理方法如下:

(1)将区域的每条边界离散后按照固定顺序排列，边界上端点的ID也依次排列。需要特别注意的是，外边界必须按照逆时针排列，外边界上的端点编号也依次由小到大排列，如图3.16所示，从点0到点36依次排列;所有内边界离散后按照顺时针排列，同样，每条内边界上端点编号依次从小到大排列。

(2)依次判断点集的Delaunay三角剖分中每个三角形的三个顶点是否位于同一边界，若某个三角形的3个顶点位于同一边界上，将3个顶点由小到大排序，并按照排序后点号组成一个新的三角形，计算该新三角形的面积，若面积＞0，则表示该三角形为区域内部三角形，保留;若面积＜0，则表示该三角形为区域外三角形，删除。

图3.16 边界处理

图3.17 二维区域的Delaunay三角剖分

如由点0、1和36组成的三角形，排序后依次为0、1、36，新的三角形面积＞0，表示该三角形为区域内部三角形，保留;由点21、22和23组成的三角形按照逆时针规则正常时排序为23、22、21，排序后依次为21、22、23，新的三角形面积＜0，表示该三角形为区域外部三角形，删除。

边界处理后，得到最终的区域的Delaunay三角剖分，如图3.17所示。

布点和离散边界的代码详见推进波前法代码中的函数CreateInnerPoint()和Create-BoundaryPoint();点集的Delauany三角剖分方法的完整代码详见Bowyer-Watson算法的代码。以下为进行边界处理的代码，函数DeletedInvalidTriangle()用于删除剖分区域之外的三角形，函数AreaOfTrgl()用于计算三角形的面积。

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

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