简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。

Fast Algorithm for Delaunay Triangulation of Simple Polygon Based on Maximum Triangle Weights

The Delaunay triangulation of simple polygon,being basic methods of calculating geometry,has been widely applied to computer graphics,3D geographic modeling. This paper presents a fast algorithm for Delaunay triangulation of simple polygon based on maximum triangle weights referring to others.The state of triangle is best or better in the result of triangulation.The correctness and efficiency of the algorithm are confirmed strictly and the algorithm's time complexity is illustrated.Finally an example is given.The tested analysis shows that for simple polygonal domains randomly generated,the algorithm is efficient in computation and has an almost linear in running time.