一种改进的Delaunay三角形化剖分方法

A MODIFIED DELAUNAY MESH GENERATION METHOD FOR 2-D DOMAIN

提出了一种基于Bowyer Watson算法的平面区域Delaunay三角化剖分的改进方法。它结合了前沿推进法的内部结点生成技术和Delaunay联点网格生成技术 ,使得每插入一点所破坏的单元尽可能地少。采用适当的数据结构 ,使Delaunay搜索过程限于局部 ,算法大为简化 ,易于编程 ,浮点计算量少 ,同时也避免了使用函数递归调用。采用在基网格上定义网格步长的办法控制网格的疏密 ,使网格疏密易于控制。几个算例表明 ,该算法是行之有效的。

A method for constructing two dimensional unstructured meshes using the Delaunay triangulation criterion is described. The algorithm is based on the Bowyer Watson's idea to construct the node links and on the advancing front method for generating the inner nodes. In the triangulation process, the latter inserted nodes may break less links by using this method. By taking the edges into the data structure, the Delaunay searching is a local process, and the recursive function calling can be avoided. So it is easy to construct the code, and the floating point computation is reduced. The mesh density is controlled through defining the mesh step on the vertices of the ground mesh. Some examples show that the algorithm is robust and effective.