What is the best way to triangulate a polygon with Boost?
I use Boost.polygon.
My current algorithm:
Compute a voronoï diagram from my polygon vertices.
Create one directed polygon-edge for each cell-edge (this will create two directed polygon edge per cell-edge)
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).
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:
See also https://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram for more background on the problem.