DELAUNAY TRIANGULATION OF NON-CONVEX PLANAR DOMAINS
DELAUNAY TRIANGULATION OF NON-CONVEX PLANAR DOMAINS
复制标题
DOI：
10.1002/nme.1620281113
复制
发表时间：
1989-11-01
影响因子：
2.9
通讯作者：
LO, SH
中科院分区：
文献类型：
--
作者：
LO, SH
本文探讨了将目前最流行的两种网格生成技术，即前沿推进法和Delaunay三角剖分算法相结合的可能性。所得到的方案的优点是它的简单性，效率和通用性。通过引入“非Delaunay”线段，阐明了Delaunay三角剖分的概念，提出了一种有效的非凸平面区域上Delaunay三角剖分的构造算法。内部节点首先在平面域内生成。然后将这些内部节点和边界节点连接在一起以生成有效的三角剖分。在网格生成过程中，每个三角形的Delaunay属性是通过选择一个节点具有最小的相关外接圆。与凸域相比，必须检查所提出的三角形与域边界之间的相交;通过对大量具有不同特征的算例的研究，发现该算法可以得到高质量的三角形单元网格，并且网格生成时间与三角剖分的单元/节点的数量具有线性关系。
This paper investigates the possibility of integrating the two currently most popular mesh generation techniques, namely the method of advancing front and the Delaunay triangulation algorithm. The merits of the resulting scheme are its simplicity, efficiency and versatility. With the introduction of ‘non‐Delaunay’ line segments, the concept of using Delaunay triangulation as a means of mesh generation is clarified.An efficient algorithm is proposed for the construction of Delaunay triangulations over non‐convex planar domains. Interior nodes are first generated within the planar domain. These interior nodes and the boundary nodes are then linked up together to produce a valid triangulation. In the mesh generation process, the Delaunay property of each triangle is ensured by selecting a node having the smallest associated circumcircle. In contrast to convex domains, intersection between the proposed triangle and the domain boundary has to be checked; this can be simply done by considering only the ‘non‐Delaunay’ segments on the generation front.Through the study of numerous examples of various characteristics, it is found that high‐quality triangular element meshes are obtained by the proposed algorithm, and the mesh generation time bears a linear relationship with the number of elements/nodes of the triangulation.