【摘要】 提出了一个在给定多边形边界的平面点集上进行三角化的方法.文中指出,一个定边界平面点集的三角化与该点集的无约束Delaunay三角化仅在称为凹链的局部区域存在不一致,二者的三角形个数与边数均有固定的关系.但是,由于Delaunay三角化无法保持边界约束,利用基于凹链的查找技术对Delaunay三角化的结果进行修正,从而得到定边界三角化结果.结果对Delaunay三角做到了最大程度的近似.更多还原

【Abstract】 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.更多还原