http://www.gissky.net- GIS空间站

分块式生成Delaunay三角网是加快构网速度的一个基本思路。已有的分治算法和其他分块合并算法能使平均时间复杂度接近线性,但算法复杂,编程难度大,且容易产生计算误差导致的错误。本文作者曾提出过一种基于三角网扩张法的逐块归并算法,它也是一种快速算法,但在算法中需要增加避免错误的判断规则,使程序变得较复杂。本文中的逐块生成法是对逐块归并法的改进,它继承了逐块归并法高效的优势,而且减少了判断规则,步骤更加简单。

Dividing the points into blocks and generating Delaunay triangulation from each block is the cardinal idea for fast creating large Delaunay triangulation.Divide-and-Conquer algorithm and other divide-and-merge method at present have the time complexity of linearity but their steps are more complex and difficult to program,and it also raises the probability of occurring bugs from float-point errors.The author of this article proposed a sequential merging algorithm based on triangle-expanding method and it's ...