New Longest-Edge Algorithms For the Refinement and/or Improvement of Unstructured Triangulations

International Journal for Numerical Methods in Engineering, Wiley, Vol 40, pp.3313-3324, 1997

MESHING
RESEARCH
CORNER

Department of Computer Science, University of Chile, Casilla 2777, Santiago, Chile

Abstract
In this paper I introduce a new mathematical tool for dealing with the refinement and/or the improvement of unstructured triangulations: the Longest-Edge Propagation Path associated with each triangle to be either refined and/or improved in the mesh. This is defined as the (finite) ordered list of successive neighbour triangles having longest- edge greater than the longest edge of the preceding triangle in the path. This ideal is used to introduce two kinds of algorithms (which make use of a Backward Longest-Edge point insertion strategy): (1) a pure Backward Longest-Edge Refinement Algorithm that produces the same triangulations as previous longest-edge algorithms in a more efficient, direct and easy-to-implement way; (2) a new Backward Longest-Edge Improvement Algorithm for Delaunay triangulations, suitable to deal (in a reliable, robust and effective way) with the three important related aspects of the (triangular) mesh generation problem: mesh refinement, mesh improvement, and automatic generation of good-quality surface and a volume triangulation of general geometries including small details. The algorithms and practical issues related with their implementation (both for the polygon and surface quality triangulation problems) are discussed in this paper. In particular, an effective boundary treatment technique is also discussed. The triangulations obtained with the LEPP- Delaunay algorithm have smallest angles greater than 30~ and are, in practice, of optimal size. Furthermore, the LEPP-Delaunay algorithms naturally generalize to three-dimensions.