How to triangulate polygons in Boost?

Question

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

I am using Boost.polygon .

My current algorithm is:

1. Compute the Voronoi diagram from my vertices of the polygon.

2. Create one directed polygon edge for each cell edge (this will create two directed polygon edges on the cell edge)

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

Is there a better solution?

Edit: I just realized that maybe you can go through the cells in a special way to create triangles directly (3 neighboring cells create a triangle).

Answer 1

The main idea is to walk along the peaks of Voronoi and create a triangle from the points of generation of each cell falling on the top of Voronoi. In the case of a degenerate vertex with degree> 3, you will need to generate more than one triangle, but this is easy to do with a fan triangle.

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 Voronoi diagram? for more information about the problem.