论文部分内容阅读
作为计算几何的基本问题,Delaunay三角剖分及其对偶图Voronoi图广泛应用于曲面重建,分子建模以及网格牛成。在众多的Delaunay三角剖分算法中,逐点插入算法是应用最广,也是目前研究得最多的算法,它具有实现简单,易于推广到高维的优点。逐点插入的Delaunay三角剖分算法主要由两部分组成:一是定位(pointlocation),即找到新插入点在当前剖分中所在的单元;二是更新(update),即将剖分更新使得包含新插入点的剖分仍然满足Delaunay性质。逐点插入算法的理论依据是往一个已经满足Delaunay性质的三角剖分中新加入一个点,可以通过有限次数的边转换(Edge flip)使得包含新插入点的剖分仍然满足Delaunay性质。逐点插入算法的效率由定位和更新决定。而点的插入顺序在其中起着关键作用。一个好的插入序一方面能提高定位的效率,另一方面也能有效减少新插入点打破剖分的单元个数。