practical algorithm for constrained triangulation in two dimensions?

Question

I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained triangulations is the discovery of edges which are intersected by the constraint, removing them, and retriangulating the hole.

AFAIK the optimal time bound for 2D constrained triangulation is o( n log n ), where n is the number of input vertices. That's what Paul Chew achieved in his paper "Constrained Delaunay Triangulations" from 1987 (he described divide and conquer algorithm, which looks difficult to implement in practice BTW). I would like to stay within that bound. But I would like to know an algorithm which is asymptotically worse if it is also much simpler.

Numerical robustness is not an issue for me.

EDIT:

The input is a Planar straight-line graph. In my particular case the graph describes a polygon with holes, so it has no unconnected vertices - then it would be a list of vertices describing the outer boundary of the polygon and the boundaries of the holes.

As output I would like to have a mesh - a collection of triangles which are represented by 3 indices into an array of vertices.

Answer 1

This does not directly answer your question, but the easiest implementation by far is to use one that already exists. Jonathan Shewchuck has written high-quality contrained Delaunay triangulation code in C++, and makes it easily available through his Triangle web page. It is fast; he quotes a runtime of 21 sec for 1,000,000 vertices.

If you want to use an inefficient algorithm, you could dispense with all efficient data structures, and use linear search whenever looking for an item. This will simplify the code.