基于邻接表的非结构网格快速生成算法

Fast Generation of Unstructured Mesh Based on Adjacency List

目的优化Delaunay方法,提高网格生成效率并通过拉普拉斯光顺化提高网格质量.方法用图这种数据结构来表示三角形网格并用邻接表存储以优化存储方式.结果该数据结构同传统结构数组算法相比时间大大缩短、提高了网格生成效率.从网格生成的算例看出,该算法不仅提高了网格生成的速度,而且生成的网格质量较好,便于局部加密.结论通过用图表示三角形网格并用邻接表优化储存,提高了网格生成效率.将生成的网格进行拉普拉斯光顺化,可使网格质量得到进一步的提高.

The generation of unstructured triangle/tetrahedral mesh is the precondition to solve the fluid flow and heat transfer in complex domain. It is of great importance to develop fast generation algorithm of unstructured mesh. According to the characteristics of Delaunay triangulation method, a fast algorithm to create unstructured mesh is proposed. In this method, triangle structure is presented by Graph and the data is stored by Adjacency List, through which the neighbor triangles can be easily found since their addresses are stored in each node. Meanwhile the time consuming of deletion, insertion and sorting operation can be saved considerably because of the property of list. Compared with the traditional algorithm based on structured array, the efficiency of the new algorithm to generate unstructured mesh can be improved dramatically. From the generated meshes, it is shown that with the new algorithm, not only the generation speed is increased, but also the quality of the mesh is better and easy to be refined. Finally, the generated mesh is smoothed by Laplace method and the mesh quality can be further improved.