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

Question

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

我使用Boost.polgon.

我目前的算法：

1. 根据我的多边形顶点计算一个voronoï图。

2. 为每个单元格边缘创建一个有向多边形边缘（这将为每个单元格边创建两个有向多边边缘）

3. 在所有创建的边上迭代以创建三角形（并非微不足道）

有更好的解决方案吗？

编辑：我刚刚意识到，可能可以用一种特殊的方式遍历单元格，直接创建三角形（3个相邻单元格创建一个三角形）。

Answer 1

主要思想是通过Voronoi顶点进行迭代，并从Voronai顶点上每个单元的生成点创建一个三角形。在阶数>3的退化顶点的情况下，您需要生成多个三角形，但使用三角扇很容易做到这一点。

使用Boost多边形：

#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());
}

另请参阅如何从Voronoï图进行三角测量？了解有关该问题的更多背景信息。