# practical algorithm for constrained triangulation in two dimensions?

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.

• Please explain in more detail what is your input and your desired output. – Neil Strickland Apr 23 '12 at 12:03