A Simplified Robust Graph-based Automatic Delaunay Triangulation Algorithm for Arbitrary 2D Domain
Feng Jian-hu · 2004
There are some applications of Delaunay triangulation for arbitrary 2D (denoted as DTAD for short) domain (including some cava), such as generation of finite element meshes. This paper proposes a simplified robust graph-based automatic algorithm of DTAD.At first, the constrained minimum spanning tree for all boundary points is constructed. According to three simplified constrained algorithms, the triangle meshes for these points are obtained by inserting an edge every time. Then DTAD is constructed automatically by using the robust local optimization algorithm and the body-fitted generating kernel algorithm.At the same time the influences of degeneracy and numerical errors to triangulation quality are also analyzed. Robustness of the local optimization algorithm is greatly improved, so it can be better used for triangulation within arbitrary 2D domain. Numerical examples are also given to illustrate the effectiveness of the method at the end of the paper.