一种基于格子分块的快速Delaunay三角剖分算法

介绍了一种基于分块格子构造的快速Delaunay平面剖分算法，先对点集以方格为单位分组，每组分别进行Delaunay三角网生成，再把分组构成的网格合并成一个整体。该算法易于理解和实现，占用内存少，运算速度快，具有近优的线性时间复杂度。最后给出的实例也证明了算法的可靠性和实用性。

A Fast Delaunay Triangulation Algorithm Based on Square-Block Makng

A block-marking algorithm for Delaunay triangulation is introduced in this paper. This algorithm suggested here divides the given set of points into groups (square grids), constructs Delaunay triangulations for individual groups, and then joins these triangulations into the whole. It has the advantage of easily understanding and realizing, less memory, fast computing speed and execution times close to linear ones. At last, an example is given to demonstrate the reliability and practicability of this algorithm.