C++ 2D tessellation library?

Question

I've got some convex polygons stored as an STL vector of points (more or less). I want to tessellate them really quickly, preferably into fairly evenly sized pieces, and with no "slivers".

I'm going to use it to explode some objects into little pieces. Does anyone know of a nice library to tessellate polygons (partition them into a mesh of smaller convex polygons or triangles)?

I've looked at a few I've found online already, but I can't even get them to compile. These academic type don't give much regard for ease of use.

Answer 1

I've just begun looking into this same problem and I'm considering voronoi tessellation. The original polygon will get a scattering of semi random points that will be the centers of the voronoi cells, the more evenly distributed they are the more regularly sized the cells will be, but they shouldn't be in a perfect grid otherwise the interior polygons will all look the same. So the first thing is to be able to generate those cell center points- generating them over the bounding box of the source polygon and a interior/exterior test shouldn't be too hard.

The voronoi edges are the dotted lines in this picture, and are sort of the complement of the delaunay triangulation. All the sharp triangle points become blunted:

Boost has some voronoi functionality: http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

The next step is creating the voronoi polygons. Voro++ http://math.lbl.gov/voro++/ is 3D oriented but it is suggested elsewhere that approximately 2d structure will work, but be much slower than software oriented towards 2D voronoi. The other package that looks to be a lot better than a random academic homepage orphan project is https://github.com/aewallin/openvoronoi.

It looks like OpenCV used to support do something along these lines, but it has been deprecated (but the c-api still works?). cv::distTransform is still maintained but operates on pixels and generates pixel output, not vertices and edge polygon data structures, but may be sufficient for my needs if not yours.

I'll update this once I've learned more.