Как триангулировать полигоны в Boost?

Question

Как триангулировать полигоны в Boost?

Каков наилучший способ триангуляции многоугольника с помощью Boost?

я использую Boost.polygon.

Мой текущий алгоритм:

Вычислить диаграмму Вороного из моих вершин многоугольника.
Создайте один направленный край многоугольника для каждого края ячейки (это создаст два направленных ребра многоугольника на край ячейки)
Итерация по всем созданным ребрам для создания треугольников (нетривиально)

Есть лучшее решение?

Редактировать: Я только что понял, что, возможно, можно пройти по ячейкам особым образом, чтобы создать треугольники напрямую (3 соседние клетки создают треугольник)

5

algorithm boost c++polygons triangulation

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Основная идея состоит в том, чтобы перебрать вершины Вороного и создать треугольник из точек генерации каждой ячейки, падающей на вершину Вороного. В случае вырожденной вершины со степенью> 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());
}

Смотрите также https://computergraphics.stackexchange.com/questions/1815/how-to-triangulate-from-a-vorono%C3%AF-diagram для получения дополнительной информации о проблеме.

5