Polygon Triangulation with Holes

Solution 1:

To give you some more choices of libraries out there:

Polyboolean. I never tried this one, but it looks promising: http://www.complex-a5.ru/polyboolean/index.html

General Polygon Clipper. This one works very well in practice and does triangulation as well as clipping and holes holes: http://www.cs.man.ac.uk/~toby/alan/software/

My personal recommendation: Use the tesselation from the GLU (OpenGL Utility Library). The code is rock solid, faster than GPC and generates less triangles. You don't need an initialized OpenGL-Handle or anything like this to use the lib.

If you don't like the idea to include OpenGL system libs in a DirectX application there is a solution as well: Just download the SGI OpenGL reference implementation code and lift the triangulator from it. It just uses the OpenGL-Typedef names and a hand full of enums. That's it. You can extract the code and make a stand alone lib in an hour or two.

In general my advice would be to use something that alreay works and don't start to write your own triangulation.

It is tempting to roll your own if you have read about the ear-clipping or sweep-line algorithm, but fact is that computational geometry algorithms are incredible hard to write in a way that they work stable, never crash and always return a meaningful result. Numerical roundoff errors will accumulate and kill you in the end.

I wrote a triangulation algorithm in C for the company I work with. Getting the core algorithm working took two days. Getting it working with all kinds of degenerated inputs took another two years (I wasn't working fulltime on it, but trust me - I spent more time on it than I should have).

Solution 2:

Jonathan Shewchuk's Triangle library is phenomenal; I've used it for automating triangulation in the past. You can ask it to attempt to avoid small/narrow triangles, etc., so you come up with "good" triangulations instead of just any triangulation.

Solution 3:

CGAL has the tool you need: Constrained Triangulations

You can simply provide boundaries of your polygon (incuding the boundaries of the holes) as constraints (the best would be that you insert all vertices, and then specify the constraints as pairs of Vertex_handles).

You can then tag the triangles of the triangulation by any traversal algorithm: start with a triangle incident to the infinite vertex and tag it as being outside, and each time you cross a constraint, switch to the opposite tag (inside if you were previously tagging the triangles as outsider, outside if you were tagging triangles as insider before).

Solution 4:

I have found the poly2tri library to be exactly what I needed for triangulation. It produces a much cleaner mesh than other libraries I've tried (including libtess), and it does support holes as well. It's been converted to a bunch of languages. The license is New BSD, so you can use it in any project.

Poly2tri library on Google Code