一种网格和节点同步生成的二维Delaunay网格划分算法

An Algorithm for Constructing 2D Delaunay Adaptive Mesh with Simultaneous Generation of Nodes and Elements

应用Lawson算法对网格的Delaunay性质进行维护,利用单元尺度场控制生成网格的疏密分布;找到任一不满足尺度场要求的单元,在其可插度最大的边上按一定法则插入新节点,加密网格,实现内节点的生成与网格划分同步进行.该算法避免了搜寻包含三角形的过程,提高了效率.通过多次划分实验表明,该算法的时间复杂度约为O(N1.2).同时,由于在不满足单元尺寸要求的单元边上插入新节点,直接对单元的边长进行控制,使得网格的质量和自适性更加良好.

The present algorithm uses Lawson algorithm to maintain mesh Delaunay property and controls mesh density through an element size field. The field grows with mesh generation. Elemental node is inserted＇one by one on the longest edge of an element which does not satisfy the size field requirements. Mesh refinement and the interior nodes generation are accomplished simultaneously. In the mesh refinement phase, the presented algorithm is efficient for it avoids the inserting point location manipulation. Empirical tests, for N up to 150000, indicate that the time complex of the algorithm is about O（N^1,2）.