|
|
本课题的研究方法
三角网格化主要有两种准则:一种称为 Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。
Delaunay的重要性质
空外接圆性质：在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。
最大最小角度性质：在由点集V生成的Delaunay三角网中，所有三角形中的最小角度是最大的，即在生成的三角形网格中,各三角形的最小内角和为最大。
唯一性：不论从区域何处开始构网，最终都将得到一致的结果。
由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网；Lingas进一步论证了“在一般情况下，Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要算法依据。
3.3 详细算法描述
算法基于上述的传统构建算法，但仅有两步：
第一步：
（1） 在离散点集中寻找一纵坐标最小的点A。
（2） 以点A为起点，寻找两个点B、D，使得向量AB与横坐标轴夹角最小，向量AD与横坐标轴夹角最大。若点A、B、D共线，将原B点标记为A，寻找点D，使得向量AD与直线AB夹角最大；寻找点C使得向量BC与线段AB夹角最小。否则，若A、B、D不共线，则寻找点C使得向量BC与线段AB夹角最小。这样，所有点都在逆时针旋转的折线DABC的左侧。
（3） 上面一步生成的点C、D如果为同一点，则△ABC（或△ABD）即为包含所有不规则点的Delaunay三角形，生成凸包的过程结束跳过一下各步；否则，继续第四步。
（4） 寻找一个距离直线AB最远的点E，过E作直线AB的平行线，与射线AD、BC分别交于点D’、C’，将点D’、C’重新标记为点D、C，则凸四边形DABC包括所有不规则点
（5） 判断△ABC的外接圆是否包含点D，若是则求△ABC的外接圆半径R，在射线BC上距点C2.1R远处取一点D’，并将点D’重新标记为点D，则凸四边形DCBA即为所求得的初始凸包。若△ABC的外接圆不包含点D，则凸四边形DCBA即为所求得的初始凸包。
第二步：不规则点内插
在原有Delaunay三角形网的基础上，将其余离散点依次内插，形成Delaunay三角网。该算法原理遵循传统（TSAI）离散点内插算法。
内插的计算机实现：
将第一步中形成的初始Delaunay三角形放入Delaunay三角形链表。并建立临时三角形链表，放置新生成的三角形，初始值为空。
（1） 若没到点集链表的尾端，按顺序取不规则点中的一个点O；将临时三角形链表清空。
（2） 若Delaunay三角形链表不为空，从该链表中按顺序取一个，称为当前三角形。若为空，转（5）。
（3） 若当前三角形的外接圆不包含点O，转（2）；否则，将当前三角形与临时链表中的所有三角形依次比较，将临时三角形链表中的与当前三角形有公共边的全部删除；并且将当前三角形中的公共边标记出，若当前三角形的公共边数达到3，转（4）
（4） 将点O与当前三角形的非公共边连接成新的三角形，放入临时三角形链表的尾部，同时从Delaunay三角形链表中删除当前三角形转（2）。
（5） 判断临时三角形链表是否为空，若否，将临时三角形中的所有三角形全部放入Delaunay三角形链表。
