一种基于三角网扩张法的Delaunay三角网逐块归并算法

本文中提出一种基于三角网扩张法的不规则三角网的逐块归并算法,它采用按横向或纵向对离散点集切割分块,对各子块用三角网扩张法构建Delaunay三角网,最后用三角网扩张法依次将相邻的子网合并。该算法采用的子集分块的做法使构网时的搜索范围减小,在数据量较大时避免了计算时间随点数的指数次增加,同时在构网时也能保证三角形邻接关系的正确维护。

A sequential Delaunay triangular networks merging algorithm based on triangle-expanding method

The paper introduces a sequential merging algorithm based on triangle-expanding method of triangular networks. This algorithm splits the discrete points set into several subset horizontally or vertically. Then it builds delaunay triangular networks on these subset by triangle-expanding method. Finally it merges these triangular networks one by one sequentially using triangle-expanding method. The splitting method of this algorithm can decrease the search scope of points remarkably and avoid the exponential increasing of time spent. It also guarantees the management of relationship between triangles.