1160
中国图象图形学报
第15卷
3)三角形的搜索及定位
根据逐点插入方法的步骤,初始Delaunay三角
网建立完成之后,就要进行点的内插。当一个点内
插到三角网中时,需要对该点所在的三角形进行定
位。定位算法是提高逐点插入方法效率的关键所在
之一。
快速定位点所在的三角形的一个重要方法就是
通过对数据进行分块管理,先定位目标点所在的块,
然后在该块管理的三角形中寻找目标三角形。这种
方法极大地缩小了搜索目标三角形的范围,提高了
定位速度Ⅲo。
John采用了基于面积坐标(或重心坐标)的关
系来定位点的方法¨51,但是计算量比较大。蒲浩等
人采用依据点与当前三角形重心与边的位置关系来
定位点的判断标准¨“,从而大大减少了运算量,其
搜索终止条件是插入点与重心相对于三角形的3条
边均位于同侧。为了进一步减少运算量,刘少华等
人采用的是点边关系方向定位算法Ⅲo。该算法能
快速找到点所在的三角形,但是其搜索路径不具有
唯一性,因为可能存在目标点同时在一个三角形两
条边的右边,当遇到这种情况时,只能选其中的一边
进行定位,这样就不能保证定位路径为最优。为了
解决搜索定位路径唯一性问题,刑建业等人提出一
种改进算法——最速方向定位算法¨¨,该算法可以
保证定位方向是最优的。如图3所示,J7v为待插入
点,M为首三角形重心,根据肘Ⅳ连线与三角形边相
交的情况来选择相应的相邻三角形进行判断,直至
找出Ⅳ点所处的三角形。
图3搜索点的示意图
Fig.3
Point
8earching
figure
但该算法没有考虑两种特殊情况:即方向线经
过三角形的顶点及方向线与三角形的边重合。当遇
到这两种情况时,算法有时会出现死循环情况。为
了解决该问题,刘少华等人进而又提出了一种基于
线一线关系的最速方向定位算法Ⅲ】,取得了比较好
的效果。
4)点插入及Delaunay三角网的优化
当在三角网中新插入一个点P后,三角网重构
~般有两种做法,一种是边交换方法:将P与其所
在三角形的3个顶点连接起来形成新的三角形,再
采用边交换进行重构优化;另一种是影响域凸包方
法:确定P的影响域凸包,将P与所有影响域凸包
顶点连接构成新三角形。
对于第1种方法,何时进行三角网的优化主要
有两种方案Ⅲ1:一种方案是,每插入一个点,便对新
的三角网进行优化;另一种方案是,三角网联结完毕
后再进行优化。前者每次优化都不同程度地浪费了
前面的优化时间,但三角形比较规整,重心分布均
匀,易于三角形查找。后者在三角网未优化之前,存
在大量狭长的、内角尖锐的小面积三角形,而内角尖
锐的三角形存在着潜在的数字精度问题,同时狭长
三角形太多,不利于三角形的查找。为了解决上述
两种方法的不足,可以采用二次优化方案B“:先插
入总点数n中的部分点√n,按一定的优化算法进行
优化,在优化后的三角网中,再将剩下的所有点插
入,最后再进行一次优化。
一般情况下相邻数据点是连续插入的,则每加
入一点,该点附近三角形受影响的概率较大,需重构
的三角形数较多。于是Bomuchaki提出了先疏后
密、随机插入的方法Ⅲ1,但这样难以保证插入点时,
所破坏的单元数目较少。另外,Rebay和Anderson
则采用先加入位于边界上的点,然后再逐点加入区
域内的点的方法"m”1,取得了比较好的效果。为了
进一步优化加入边界点的过程,邬吉明等人提出将
加入的点按照均匀分布的原则排序,然后采用相邻
排列、分级加入的思想来提高优化效率¨2。。
在对复杂区域进行剖分,特别是边界尺度对比
较大或是点集分布极为不规则时,Delaunay算法判
断一点在圆内还是圆外,有时会因浮点运算的舍入
误差导致判断失误,以致程序非正常中断。徐明海
等人建议采用双精度数据类型计算圆心及调整影响
域空腔来解决此问题p“,但似乎并不彻底。因此刘
士和等人提出以排序过程代替以往算法中形成新三
角形时部分复杂的搜索过程∞引,提高了计算效率的
同时,也解决了由于判断误差导致“多米诺骨牌效
应”以致程序非正常中断问题。Ely和Leclere则采
用将不精确的点用小圆盘来代替的方法旧引。又因
为不精确的点是由不精确的茗坐标和y坐标导致,
所以Khanban和Edalat用矩形来代替小圆盘以表示
万方数据