一种简单快速的Delaunay三角网逐块生成算法

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

A simple and quick block-by-block generating method for generating delaunay triangulation from points in the plane

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 average time complexity is close to O(n),but in order to avoid float-point bugs,a judging rule must be added and thus the steps is some more complicated.The block-by-block generating method in this article is an improved modification of sequential merging method and inherits the high efficiency but more simple.