Delaunay triangulation of non-convex planar domains

Abstract

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. 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.