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

问题描述

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

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

我使用 Boost.polygon .

我当前的算法:

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

1. 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)

有更好的解决方案吗?

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

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).

推荐答案

主要思想是迭代Voronoi顶点，并从入射在Voronoi顶点上的每个像元的生成点创建一个三角形.对于度数大于3的简并顶点，则需要生成多个三角形，但是使用三角形扇子很容易做到这一点.

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.

使用Boost多边形:

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

另请参见如何从Voronoï图进行三角剖分?以获得更多有关该问题的背景.

See also How to triangulate from a Voronoï diagram? for more background on the problem.

这篇关于如何在Boost中对多边形进行三角剖分?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！