离散点集实时Delaunay三角网剖分算法的研究

Study on the Algorithm for Instantly Generating Delaunay Triangulation of Planar Scattered Point Set

为了解决分治算法、插入算法和生长算法都要求在构网之前给出所有点数据这个问题,实时三角网剖分算法先利用部分离散点生成一个外轮廓为凸包的初始三角网。然后将点加入到既有三角网中,如点落在既有三角网的某一三角形中,将该点与三角形的顶点相连构建新的三角网;如点落在既有三角网外,找出该点向既有三角网外轮廓围成的凸包发出的两条支撑线,这两条支撑线与既有凸包围成了一个多边形,再将这个多边形剖分成三角网即可。最后利用局部优化算法对所生成的三角网进行优化,使之成为Delaunay三角网。该算法构网时无需预先给定所有数据点,可用于实时生成三角网;此外,通过对凸包进行分区管理,在搜寻凸包支撑线时,能预先确定出支撑点的范围,减少了搜索工作量,提高了三角网的生成速度。

In order to solve the problem that all of the divideandconquer algorithm, the insert algorithm and the developing algorithm require the data of all points ahead of generating triangulation, First, the Algorithm for Instantly Generating Delaunay Triangulation uses some points to form a triangular mesh with a convex polygon boundary. Then connects the rest points with the existing mesh to generate new mesh. If a point is located into a triangle, it shall join the point and the vertices of the triangle to update the mesh; if a point is located outside the existing mesh, it shall find the two support lines from the point to the boundary convex polygon, the two lines and the boundaries shall generate a polygon, cutting the polygon into triangles to form a new mesh. Eventually, local optimization procedure is adopted to turn the mesh into Delaunay triangulation. The algorithm is suitable for instantly generating triangulation because it can generate triangles when partial points are given. Moreover, the algorithm utilizes subareas to control the vertices of convex hull so that the range of support points can be predefined when searching support lines, thus the work of searching support points can be reduced and the speed of triangulation generating raised.