carrier image

Non-Obtuse Boundary Delaunay Triangulations

Hitschfeld, Nancy and M. Cecilia Rivara

Proceedings, 6th International Meshing Roundtable, Sandia National Laboratories, pp.391, October 1997


Nancy Hitschfeld and M. Cecilia Rivara
Dpto. Ciencias de la Computacion, Univ. de Chile
Blanco Encalada 2120, Santiago, CHILE
e-mail: and

In this paper we discuss the construction of Non-obtuse Boundary Delaunay triangulations of general polygons such as needed in @te volume methods applications. These are Delaunay triangulations such that the boundary triangles do not have obtuse angles opposite to any boundary edge or interface edge. The method we propose in this paper, based on the use of longest-edge bisection techniques, consists on two steps: (1) The construction of a good quality (constrained) Delaunay triangulation of the polygon having interior angles bounded by 30' and 1200; (2) A postprocess step which eliminates boundary obtuse triangles by combining longest-edge insertion points, the Delaunay algorithm and a special treatment for boundary triangles with two boundary edges.

The construction of the good quality (constrained) Delaunay triangulation consists of-(a)The generation of any constrained Delaunay triangulation, and b) the use of an algorithm that improves the quality of the mesh so that the minimum angle is greater than or equal to 300. For the improvement of the mesh, we use an algorithm that uses a LEPP-Delaunay improvement algorithm in interior triangles and a special boundary treatment over boundary triangles. The basic LEPP-Delaunay improvement strategy uses the Longest-Edge Propagation Path of the target triangles (to be either refined and/or improved in the mesh) in order to decide which is the best point to be inserted, to produce a good-quality distribution of points. This strategy is repeatedly used until the target triangle is destroyed. The special boundary treatment technique both avoids the insertion of undesirable points in the neighborhood of the boundary and contributes to a better point distribution.

The post-processing to eliminate boundary triangles (with largest angle smaller than or equal to 120 degrees considers three cases: (a) triangles with only boundary edge which is opposite to an obtuse angle, (b) triangles with two boundary edges and one of them opposite to an obtuse angle, and (c) triangles with three boundary edges. The case (a) is solved by inserting the mid-point at the boundary edge. Since the obtuse angle is smaller than 120', no diagonal interchange is necessary. For the case (b) and since the insertion of a point on the longest-boundary edge keep the obtuse angle in the new triangle with two boundary edges, we propose to insert two points so that the new boundary triangle with two boundary edges is isosceles. A triangle with three boundary edges (case (c)) is a very rare case. Depending on the angles of the triangle, one or two isosceles triangles with two boundary edges are generated.

The post-processing strategy can be extended to handle interfaces. For obtuse triangles with one interface edge the slime strategy as for case (a) is applied. There is no need of diagonal interchange. For interface triangles with two or more interface edges adjacent to other triangles of the same type, we also propose the generation of isosceles triangles for the new triangles which keeps two interface edges.

As a corollary, the final mesh without obtuse angles at the boundary and interfaces is a Delaunay triangulation also for the triangles lying at the boundary and interface.

Download Full Paper (PDF)

Contact author(s) or publisher for availability and copyright information on above referenced article