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

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

作　　者：刘建新[1] 卢新明[1] 岳昊[1] 

机构地区：[1]山东科技大学信息科学与工程学院,山东青岛266510

出　　处：《计算机技术与发展》2006年第7期126-128,185,共4页Computer Technology and Development

摘　　要：简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。The Delaunay triangulation of simple polygon, being basic methods of calculating geometry, has been widely applied to computer graphies,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 correemess 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.

关 键 词：多边形 三角形权值 DELAUNAY三角剖分 时间复杂度 计算几何 

分 类 号：O18[理学—数学] TP301.6[理学—基础数学]