摘要
介绍了一种基于分块格子构造的快速Delaunay平面剖分算法,先对点集以方格为单位分组,每组分别进行Delaunay三角网生成,再把分组构成的网格合并成一个整体。该算法易于理解和实现,占用内存少,运算速度快,具有近优的线性时间复杂度。最后给出的实例也证明了算法的可靠性和实用性。
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.
出处
《计算机与数字工程》
2007年第2期9-10,20,共3页
Computer & Digital Engineering
