三维点集Delaunay三角剖分的自动生成与修改算法

ALGORITHMS FOR AUTOMATIC GENERATION AND DYNAMIC MODIFICATION OF THREE-DIMENSIONAL DELAUNAY TRIANGULATION

本文在已有算法的基础上，提出了一个三维点集Ｄｅｌａｕｎａｙ三角剖分的自动生成及其修改算法。自动生成算法对点在空间的位置没有任何限制，修改算法充分利用已完成的计算量，当动态增加或减少一点时，仅在局部进行适当的调整即可保证整体三角剖分符合Ｄｅ－ｌａｕｎａｙ性质。文中给出了算法正确性的证明。

In this paper,algorithms for generating and modifying Delaunay triangulation of 3Dpoint set are presented.No limitation is imposed on the location of the 3D data points in thetwo algorithms.While a point is inserted or deleted,only the modification in the local areaclose to that point is required to make the global triangulation match the Delaunay feature.The proof of the algorithm’s feasibility is given.