复杂多边形的Delaunay三角剖分研究

Delaunay Triangulation of Complex Polygons

针对复杂多边形,提出了一种基于约束边的Delaunay三角剖分算法。该算法首先建立了多边形顶点的初始Delaunay三角网,然后将多边形的各条边通过局部更新依次嵌入已有的三角网,最后再删除多余的三角形。研究结果表明,该算法生成的三角网形态优良,符合多边形的Delaunay三角剖分要求。

This paper proposed an algorithm for Delaunay triangulation of complex polygons based on constrained edges.The algorithm first constructed the initial Delaunay triangulation of polygon vertices.Then each edge of polygon is interpolated to the existent triangulation in turn through local updating, finally the redundant triangles are removed.The algorithm is concise and the triangulation generated is in good shape.