Polygon Triangulator - Ear Clipping Method

Here's a very useful code snippet. It performs polygon triangulation on a set of planer 2d or 3d data points. It supports concave polygons but not polygons with holes.

This implementation uses the standard ear clipping algorithm which decomposes the polygon into convex pieces. The API is really straightforward and easy to use.

First create an instantiation of the triangulator class:

Triangulator *t = createTriangulator();

Next, add the set of points which define the polygon contour. You can add the points as either floats or doubles; internally is uses double precision. If your polygon is 2d, just pass zero for the z component.

Example: t->addPoint(x,y,z);

To perform the triangulation itself you call:

unsigned int tcount;
unsigned int *indices = t->triangulate(tcount,epsilon);

This will return the number of triangles produced (stored in tcount) and a pointer to the array of triangle indices in the form of (a1,b1,c2, a2,b2,c2, a3,b3,c3, ....).

The value 'epsilon' is a threshold that determines whether or not a line segment in the polygon is considered co-linear or not. Since we are dealing with floating point numbers there can be inherent precision issues. Internally the triangulator operates at double precision.

If you want to retrieve the original data points, based on the index, you cal call 'getPoint'.

The implementation computes the bounding box for the input polygon and selects the two longest sides to perform the 2d triangulation against.

If you want to triangulate another polygon, just call 't->reset()' and start adding the new points.

When you are done with the triangulator class call: releaseTriangulator(t)

This code snippet uses the 'PIMPLE' paradigm (pointer to implementation) which is my favorite pattern.

The primary benefit of this code is that it is nicely packaged in snippet form.

The header file is: Triangulator.h
and the implementation in: Triangulator.cpp

Also, the FloatMath library has been revised to use this implementation internally.

FloatMath.h
FloatMath.inl
FloatMath.cpp