A variational formulation of the fast marching eikonal solver |

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
H-4). 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:

- First, the boundary nodes are triangulated.
- Boundary edges are inserted incrementally.
- If a boundary edge is not present in the triangulations, it is split in half, and the middle node is inserted into the triangulation. This operation is repeated for the two parts of the original boundary edge and continues recursively until all the edge parts conform.
- If at some point during the incremental process, a boundary edge
violates the Delaunay criterion (the
*InCircle*test), it is split to assure the conformity.

conform
An illustration of conforming triangulation.
The left plot shows a triangulation of 500 random points; the
triangulation in the right plot is conforming to the embedded
boundary. Conforming triangulation is a genuine Delaunay
triangulation, created by adding additional nodes to the original
distribution.
Figure A-4. |
---|

To insert an edge into the current triangulation, I use the following recursive algorithm:

FunctionInsertEdge()

- Define to be the midpoint of .
- Using the triangle tree structure, locate triangle that contains in the current triangulation.
**If**is an edge of**then return**.**If**(or ) is a vertex of (for example, )**then**define as an intersection of and .**Else**define as an intersection of and an arbitrary edge of (if such an intersection exists).- Insert into the triangulation.
**InsertEdge**().**InsertEdge**().

The intersection point of edges and is given by the formula

(16) |

(17) |

If, at some stage of the incremental construction, a boundary edge
fails the Delaunay *InCircle* test for the circle ,
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.

A variational formulation of the fast marching eikonal solver |

2013-03-03