如何在 Boost 中进行多边形三角剖分？

Question

什么是使用Boost三角剖分多边形的最佳方法？

我使用Boost.polygon。

我的当前算法：

1. 从我的多边形顶点计算一个voronoï图。 2. 为每个单元边创建一个有向多边形边（这将为每个单元边创建两个有向多边形边）。 3. 迭代所有创建的边以创建三角形（不是简单的）。

有更好的解决方案吗？

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

- arthur.sw

---

只是为了澄清一下：这些多边形是凸多边形吗？ - m69 ''snarky and unwelcoming''

不一定，它们可以有空洞；但是它们并不复杂。 - arthur.sw

Answer 1

主要思路是遍历沃罗诺伊顶点，并从每个与沃罗诺伊顶点相邻的单元的生成点创建一个三角形。对于度数> 3的退化顶点，则需要生成多个三角形，但可以使用三角形扇轻松完成。

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

请参阅如何从Voronoï图中进行三角剖分？了解更多有关此问题的背景信息。

- Giovanni Funchal