In the practice of mesh generation, the input nodes are often supplemented by boundary edges: geologic interfaces, seismic rays, and so on. It is often desirable to preserve the edges so that they appear as edges of the triangulation Albertin and Wiggins (1994). One possible approach is constrained triangulation, which preserves the edges, but only approximately satisfies the Delaunay criterion Chew (1989); Lee and Lin (1986). An alternative, less investigated, approach is conforming triangulation, which preserves the ``Delaunayhood'' of the triangulation by adding additional nodes Hansen and Levin (1992) (Figure 9). Conforming Delaunay triangulations are difficult to analyze because of the variable number of additional nodes. This problem was attacked by Edelsbrunner and Tan (1993), who suggested an algorithm with a defined upper bound on added points. Unfortunately, Edelsbrunner's algorithm is slow in practice because the number of added points is largely overestimated. I chose to implement a modification of the simple incremental algorithm of Hansen and Levin. Although Hansen's algorithm has only a heuristic justification and sets no upper bound on the number of inserted nodes, its simplicity is attractive for practical implementations, where it can be easily linked with the incremental algorithm of Delaunay triangulation.
The incremental solution to the problem of conforming triangulation can be described by the following scheme:
To insert an edge AB into the current triangulation, I use the following recursive algorithm:
Function InsertEdge (AB)
- Define C to be the midpoint of AB.
- Using the triangle tree structure, locate triangle that contains C in the current triangulation.
- If AB is an edge of then return.
- If A (or B) is a vertex of (for example, A = D) then define C as an intersection of AB and EF.
- Else define C as an intersection of AB and an arbitrary edge of (if such an intersection exists).
- Insert C into the triangulation.
- InsertEdge (CA).
- InsertEdge (CB).
The intersection point of edges AB and EF is given by the formula
If, at some stage of the incremental construction, a boundary edge AB fails the Delaunay InCircle test for the circle CABD, then I simply split it into two edges by adding the point of intersection into the triangulation. The rest of the process is very much like the process of edge validation in the original incremental algorithm.