基于凹链邻域修正的定边界平面点集三角化方法  

A Triangulation Method for Fixed Boundary Planar Point Set Based on Modifying of Delaunay Triangles at Concave Links

作　　者：季晓东[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250101

出　　处：《德州学院学报》2010年第2期59-62,共4页Journal of Dezhou University

摘　　要：提出了一个在给定多边形边界的平面点集上进行三角化的方法.文中指出,一个定边界平面点集的三角化与该点集的无约束Delaunay三角化仅在称为凹链的局部区域存在不一致,二者的三角形个数与边数均有固定的关系.但是,由于Delaunay三角化无法保持边界约束,利用基于凹链的查找技术对Delaunay三角化的结果进行修正,从而得到定边界三角化结果.结果对Delaunay三角做到了最大程度的近似.In this paper, we provide a new method for triangulation on fixed boundary planar point set. It is shown that the triangulation difference to unbounded Delaunay Triangulation is limited to the regions we call concave links. There is linear relation between the numbers of triangles and edges of those triangulations. Because Delaunay Triangulation do not satisfy the fixed boundary, we modify the triangles in the neighbourhood of concave links to get the right triangulation. Our result is the most similar to Delaunay Triangles.

关 键 词：平面点集 DELAUNAY三角化 欧拉公式 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]