一种新型的逐点插入Delaunay三角剖分算法插入序

摘要

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