快速Delaunay逐点插入网格生成算法

A Fast Mesh Generation Algorithm with Point-by-Point Delaunay Insertion

对插入形心的Delaunay逐点插入算法,提出按单元可插度分组的双向链表组数据结构,避免了对最大可插度单元的搜索。采用了邻接单元搜索、双向链表存储、随机方向搜索、邻接旋转、几何量继承等技术,使算法的计算时间与生成单元数近似呈线性关系,时间复杂度达到O(N1.05),N为生成单元数。算例表明,在一台AMD Athlon3200+(主频2.0 GHz)PC上,该算法的四面体单元生成速度达50 000个/s以上。

A grouped double link data structure corresponding to element inserting coefficient （EIC） is presented to eliminate the search for the maximum EIC element in the point-by-point center insertion algorithm. Adjacency search, double linked element list, random direction search, adjacency rotation, and heredity of geometrical quantities are applied to increase the efficiency of mesh generation. The relationship between the computing time and the number of generated elements is nearly linear and the time complexity is O（ N^1.05 ）, where N is the number of elements. Example shows the generating rate of this algorithm is above 50 000 tetrahedrons per second on an AMD Athlon 3200 ＋ （2.0 GHz） personal computer.