基于生长算法构建Delaunay三角网的研究

提出了一种基于凸包构建Delaunay三角网的算法,它包括离散点数据的三角剖分及将约束边嵌入三角网。在对离散点数据进行三角剖分时,首先建立一个外轮廓为凸包的初始三角网,然后将剩余的点依次与既有三角网合并来生成包含所有数据点的三角网。为了将约束边嵌入三角网,找出约束边穿过的三角形,删除这些三角形并用约束边将这些三角形所围成的多边形分成两个简单多边形,再对这两个简单多边形进行Delaunay三角网剖分即可达到嵌入约束边的目的。

Study on Growth Algorithm for Generating Constrained Delaunay Triangulation

A algorithm for creating Delaunay Triangulation based on convex hull is presented in the paper.It includes triangulation of scattered points and inserting constrained edges into triangular meshes.When triangulating of scattered points,the algorithm creates an initial triangular mesh the boundary of which is a convex hull,then merges the other points with the existed triangular mesh to create a triangular mesh including all data points.In order to insert a constrained edge into a triangular mesh,the algorithm finds out the triangles which intersect with the constrained edge,then deletes the triangles and splits the polygon which consists of the triangles into two polygons,finally the boundary can be inserted into the triangular mesh after triangulating of the two polygons.