How to triangulate polygons in Boost?

Question

What is the best way to triangulate a polygon with Boost?

I use Boost.polygon.

My current algorithm:

1. Compute a voronoï diagram from my polygon vertices.

2. Create one directed polygon-edge for each cell-edge (this will create two directed polygon edge per cell-edge)

3. Iterate over all created edges to create triangles (not trivial)

Any better solution?

Edit: I just realized that it is probably possible to walk through the cells in a special way to create the triangles directly (3 neighbor cells create a triangle).

Niobous

Just to be clear: are these polygons convex? – Balneology

Not necessarily, and they can have holes ; but they are not complex. – Niobous

Answer 1

The main idea is to iterate through the Voronoi vertices, and create a triangle from the generating points of each cell incident on the Voronoi vertex. In the case of degenerate vertex with degree > 3 then you'll need to generate more than one triangle, but that is easily done using a triangle fan.

Using Boost Polygon:

#include "boost/polygon/voronoi.hpp"

std::vector<Point> vertices;
// add your input vertices

boost::polygon::voronoi_diagram<double> vd;
boost::polygon::construct_voronoi(vertices.begin(), vertices.end(), &vd);

for (const auto& vertex: vd.vertices()) {
    std::vector<Point> triangle;
    auto edge = vertex.incident_edge();
    do {
        auto cell = edge->cell();
        assert(cell->contains_point());

        triangle.push_back(vertices[cell->source_index()]);
        if (triangle.size() == 3) {
            // process output triangles
            std::cout << "Got triangle:" << triangle << std::endl;
            triangle.erase(triangle.begin() + 1);
        }

        edge = edge->rot_next();
    } while (edge != vertex.incident_edge());
}

See also How to triangulate from a Voronoï diagram? for more background on the problem.

Sisal

For non-convex polygons (and possibly polygons with holes), it is needed to check whether the centerpoint of the found triangle lies inside the polygon. Use boost::polygon::contains() for the check near `// process output triangles``. – Gangplank