Finite element triangulation of complex regions using computational geometry

Mesh generation is an important, resource consuming part of finite element analysis and should be carried out automatically as much as possible. For this purpose, we present a method for producing a triangulation of a complex polygonal region of the plane. The method allows the desired number of triangles and a mesh smoothness parameter to be specified along with the polygonal curves of the region's boundary. Computational geometry techniques are used to decompose and triangulate the region. The method proceeds in three stages. In the first stage, the region is decomposed into convex polygons such that small interior angles are avoided. In the second stage, a mesh distribution function is defined based on the boundary length scales and the region is further decomposed into convex polygons such that the variation of the function in each subregion is limited, since we aim to produce a triangulation which is approximately equidistributing with respect to the function. In the third stage, a Delaunay triangulation is constructed in each subregion using a quasi-uniform grid whose spacing is determined from the mesh distribution function. The computational complexity and correctness of algorithms in the three stages are discussed. We have implemented an experimental prototype of the method in PASCAL and carried out tests of triangulations for a variety of regions. We report on the performance of the method for major computational experiments on two complex test regions.