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.


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.

  • $\begingroup$ Please explain in more detail what is your input and your desired output. $\endgroup$ Apr 23, 2012 at 12:03

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.