如何在Boost中对多边形进行三角测量？

使用Boost对多边形进行三角测量的最佳方法是什么？

我使用Boost.polygon.

我目前的算法:

从我的多边形顶点计算voronoï图.

为每个单元格边创建一个有向多边形边(这将为每个单元格边创建两个有向多边形边)

迭代所有创建的边以创建三角形(不是微不足道的)

更好的解决方案？

编辑:我刚刚意识到可能以特殊方式遍历单元格直接创建三角形(3个相邻单元格创建一个三角形).

主要思想是迭代Voronoi顶点,并从Voronoi顶点上入射的每个单元的生成点创建一个三角形.在度数> 3的退化顶点的情况下,您将需要生成多个三角形,但使用三角形扇可以轻松完成.

使用Boost :: Polygon:

#include "boost/polygon/voronoi.hpp"

std::vector vertices;
// add your input vertices

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

for (const auto& vertex: vd.vertices()) {
    std::vector 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());
}

有关该问题的更多背景信息,另请参阅https://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram.