北京大学学报(自然科学版)

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

李水乡1, 3,陈斌1,赵亮1,刘曰武2   

  1. 1北京大学工学院,湍流与复杂系统国家重点实验室,北京,100871;2中国科学院力学研究所,北京,100080;3通讯作者,E-mail:lsx@pku.edu.cn
  • 收稿日期:2006-05-15 出版日期:2007-05-20 发布日期:2007-05-20

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

LI Shuixiang1, 3CHEN Bin1ZHAO Liang1, LIU Yuewu2   

  1. 1College of Engineering, Peking University; State Key Labrotary for Turbulence and Complex System Study, Beijing, 100871; 2Institute of Mechanics, Chinese Academy of Sciences, Beijing, 100080; 3Corresponding Author, E-mail:lsx@pku.edu.cn
  • Received:2006-05-15 Online:2007-05-20 Published:2007-05-20

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

关键词: 有限元, 网格生成, Delaunay三角化, 逐点插入算法, 单元可插度

Abstract: 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(N1.05),N, 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.

Key words: FEM, mesh generation, delaunay triangulation, point, by, point insertion, element inserting coefficient

中图分类号: