论文部分内容阅读
针对三维地层表示中散乱点的三角化问题,提出了一种新的剖分算法———环形三角剖分算法.该算法首先在散乱点中心构造初始三角形,并将其3条边作为初始环形路径;然后对环形路径上的每条线段,都在其外围寻找与两端点所成夹角最大的点构造新三角形,并将其纳入环形路径,从而使环形路径不断向外围扩展;重复此扩展过程直到所有散乱点都处于路径范围内.对上述剖分中遗漏的小块区域形成的“空洞”,利用简单多边形的三角剖分方法实现三角化.此算法时间复杂性介于Ο(n)与Ο(n2)之间,其效率体现在:只搜索外围散乱点,减少了夹角计算过