Polygon Triangulation Using Monotone Polygons

Question

I have a simple polygon without holes, and it needs to be triangulated into convex polygons for use in the physical engine, and also therefore I can use these convex polygons for rendering through triangular stripes.

This Wikipedia article shows how monotone polygons can be used to triangulate a polygon. It gives a brief description of how this works, but not enough detail for me. This method seems perfect for what I need, and the Flash Demo that it refers to shows that the algorithm works fine for my needs.

I searched Google for a better explanation of the algorithm, and I can only find libraries or source code that do triangulation. I would rather find out how it works and write my own method, but if I need to use a pre-written library, I will need to do this.

Can someone give an explanation or resources for how I can find out how this type of triangulation works?

Answer 1

The CGAL library provides several implementations of convex decomposition of simple polygons without holes. Look at chapter .

Answer 2

I suggest you take a look at the triangulations of Delaney: Wikipedia . QHull is a standard implementation. (As a benchmark, MATLAB relies on Qhull: reference .

If Qhull is not your thing, try this collection .