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

北京大学学报（自然科学版）

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

李水乡^{1, 3},陈斌¹,赵亮¹,刘曰武²

¹北京大学工学院,湍流与复杂系统国家重点实验室,北京,100871;²中国科学院力学研究所,北京,100080;³通讯作者,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 Shuixiang^{1, 3}CHEN Bin¹ZHAO Liang¹, LIU Yuewu²

¹College of Engineering, Peking University; State Key Labrotary for Turbulence and Complex System Study, Beijing, 100871; ²Institute of Mechanics, Chinese Academy of Sciences, Beijing, 100080; ³Corresponding Author, E-mail:lsx@pku.edu.cn

Received:2006-05-15 Online:2007-05-20 Published:2007-05-20

摘要/Abstract

摘要： 对插入形心的Delaunay逐点插入算法,提出按单元可插度分组的双向链表组数据结构,避免了对最大可插度单元的搜索。采用了邻接单元搜索、双向链表存储、随机方向搜索、邻接旋转、几何量继承等技术,使算法的计算时间与生成单元数近似呈线性关系,时间复杂度达到O(N^1.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(N^1.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

中图分类号:

TP391

李水乡,陈斌,赵亮,刘曰武. 快速Delaunay逐点插入网格生成算法[J]. 北京大学学报（自然科学版）.

LI Shuixiang,CHEN Bin,ZHAO Liang,LIU Yuewu. A Fast Mesh Generation Algorithm with Point, by, Point Delaunay Insertion[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2007/V43/I3/302

[1]	宋思宇, 于向前, 陈鸿飞, 陈傲, 施伟红, 邹鸿. 内部充放电监测器仿真及地面实验研究[J]. 北京大学学报自然科学版, 2021, 57(2): 209-214.
[2]	姚永芳, 孙振旭, 刘文, 杨国伟. 高速列车受电弓气动噪声特性分析[J]. 北京大学学报自然科学版, 2020, 56(3): 385-398.
[3]	刘钰洋, 刘诗琦, 潘懋, 雷征东. 基于三维角点网格模型的现今地应力有限元模拟[J]. 北京大学学报自然科学版, 2019, 55(4): 643-653.
[4]	殷有泉, 邸元, 姚再兴. 非线性有限元方程组的弧长延拓算法[J]. 北京大学学报自然科学版, 2017, 53(5): 793-800.
[5]	张庆莲,侯贵廷,潘校华,万伦坤,刘计国. Muglad盆地形成力学机制的有限元数值模拟[J]. 北京大学学报（自然科学版）, 2013, 49(6): 981-985.
[6]	胡慧琳,谭云华,朱柏承,周乐柱,单睿. 介质圆锥对数螺旋天线特性的理论研究[J]. 北京大学学报（自然科学版）, 2012, 48(2): 193-199.
[7]	高耀东,何建霞,乔云芳. 焊接过程有限元分析[J]. 北京大学学报（自然科学版）, 2010, 46(6): 1007-1009.
[8]	赵雪岩, 黄任含, 楼航迪, 荣起国. 阻塞性睡眠呼吸暂停综合征的生物力学研究[J]. 北京大学学报（自然科学版）, 2009, 45(5): 737-742.
[9]	柯敢攀,黄清华. 井地电法的三维正反演研究[J]. 北京大学学报（自然科学版）, 2009, 45(2): 264-272.
[10]	李旭东,叶琳,刘凯欣. 钢-水泥砂浆石界面动态粘结强度的实验与计算研究[J]. 北京大学学报（自然科学版）, 2008, 44(1): 1-5.
[11]	年丰,董硕,周乐柱,夏明耀. 三维电磁辐射问题混合阶矢量基有限元完全匹配层方法的研究[J]. 北京大学学报（自然科学版）, 2007, 43(1): 119-124.
[12]	徐学军,郑玉峰. 口腔生物力学问题有限元分析的研究进展[J]. 北京大学学报（自然科学版）, 2006, 42(3): 412-419.
[13]	赵小莹,周乐柱. 一种新型的可调性能的铁氧体EBG的特性分析[J]. 北京大学学报（自然科学版）, 2006, 42(3): 375-379.
[14]	赵小莹,周乐柱. 不同参量的二维介质电磁带隙的反射及传输特性研究[J]. 北京大学学报（自然科学版）, 2005, 41(3): 460-464.
[15]	班永灵, 周乐柱, 于哲峰, 王湃. 单轴各向异性背腔式微带贴片天线的表面缝隙场分布及交叉极化方向图分析[J]. 北京大学学报（自然科学版）, 2004, 40(3): 498-504.