一种常用的二维任意域的Delaunay三角剖分算法的健壮性补充  

Robust Supplement to A Delaunay Triangulation Algorithm on 2D Arbitrary Polygon

作　　者：杨磊 吴涛 

机构地区：[1]华东理工大学石化学院石化研究所,上海200540 [2]华东理工大学石化学院自动化系,上海200540

出　　处：《中国图象图形学报（A辑）》2000年第4期323-326,共4页Journal of Image and Graphics

摘　　要：由于对任意给定的平面点集通过 Delaunay三角剖分进行处理可得到具有整体最优性的三角形网格 ,因而该方法得到了广泛的重视 .但研究发现 ,常用的二维任意域 Delaunay三角剖分算法 [1 ,2 ]是有缺陷的 ,它在构成Delaunay三角形候选点的选择过程中 ,可以使候选点出现“位置违约”的错误 ,即在候选节点链表中 ,虽然可出现依据算法的判据有条件成为 Delaunay三角形的构成点 ,但采用该点构成 Delaunay三角形后 ,将违背 Delaunay三角剖分“约束圆准则”,这样会导致不正确的剖分结果 ,因此 ,该文就这一问题进行了分析和讨论 ,并给出了可行的改进方案 ,即通过调整原算法的数据结构或修改原算法的 Delaunay三角剖分判据 ,以提高算法的健壮性 ,从而得到令人满意的 Delaunay三角剖分网格 .前一种改进方案主要是重新调整了算法的数据结构 ,这虽然对算法的健壮性有较大的帮助 ,但对于已经将算法进行了应用的情形并不合适 。Attention was focused on Delaunay triangulation for its processed result is whole optimization. While according to the study on some Delaunay triangulation algorithms, there is a bug in a common Delaunay triangulation algorithm [1,2] on 2D arbitrary polygon. According to the judge rule of the algorithm, it is possible to make result of Delaunay triangulation wrong with the effect of the “irregular position” vertex of polygon, “irregular position” vertex is the vertex which is in the candidate vertex set during the processing, but would break the “in\|circle” rule of classical Delaunay triangulation if that vertex is selected for Delaunay triangle in the end. This question was analyzed and discussed in the paper, and then an improvement upon the algorithm is presented, i.e, adjusting the data structure of algorithm or modifying the judge rule to make the resultant triangle set correct and satisfied, the former method is better than the latter, but it costs more to the original algorithm.

关 键 词：Delaunay三解剖分算法 计算几何 网络划分 

分 类 号：O182[理学—数学]