二维点集三角剖分的动态生成与修改

Dynamic Generation and Modification for Triangulation of Two-dimensional Points Set

本文在已有算法的基础上提出了一个二维点集三角剖分的动态生成与修改算法。当点逐个增加或删除时,只需进行局部剖分即可保证整体三角剖分符合Delaunay性质,对点的插入位置及删除顺序未加任何限制。本文还给出了关于这一算法正确性的证明及算法复杂性分析。 本算法可应用于二维点集一阶Voronoi图的动态生成与修改,其基本思想可以扩展到三维空间。

In this paper, an algorithm for generating and modifying triangulation of 2D points set dynamically is presented.While the points are inserted or deleted individually step by step, only the triangulation in local area is needed to make the global triangulation matching the Delaunay Feature. No limitation is impos ed on the location or order for inserting and deteting points. The proof of this algorithm and the analysis of the algorithm complexity are also given,This algorithm may also be used to generate one-order Voronoi Diagram dyn amically and eztended to 3D spacc.