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

A Fast Delaunay Triangulation Algorithm Based on Square-Block Making

作　　者：陈慧群[1] 陈少克[1] 

机构地区：[1]汕头大学机械电子工程系,汕头515063

出　　处：《计算机与数字工程》2007年第2期9-10,20,共3页Computer & Digital Engineering

摘　　要：介绍了一种基于分块格子构造的快速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.

关 键 词：格子分块算法 DELAUNAY三角剖分 合并 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]