带约束折线的平面散点集Delaunay三角剖分

Delaunay Triangulation of 2D Scattered Point Set with Constrained Polylines

首先将原始散点与约束点一起进行三角剖分,形成初始Delaunay三角网,然后再将各条约束线段通过局部更新,依次嵌入已存在的三角网中,从而生成带有约束折线的平面散点集的Delaunay三角剖分。该算法思路简捷,易于编程,生成的三角网形态优良。

This paper first triangulates the original scattered points with all constrained points to form the initial Delaunay triangulation.Then each constrained segment is embedded in the existent triangulation in turn through local updating,eventually to form the Delaunay triangulation with constrained polylines.The algorithm is concise and easy to program and the generated triangulation is in good shape.