使用 Boost 对多边形进行三角剖分的最佳方法是什么?
我使用 Boost.polygon .
我目前的算法:
根据我的多边形顶点计算 voronoï 图。
为每个单元格边创建一个有向多边形边(这将为每个单元格边创建两个有向多边形边)
遍历所有创建的边以创建三角形(不简单)
有更好的解决方案吗?
编辑:我刚刚意识到可以以一种特殊的方式遍历单元格以直接创建三角形(3 个相邻单元格创建一个三角形)。
最佳答案
主要思想是遍历 Voronoi 顶点,并根据入射到 Voronoi 顶点的每个单元格的生成点创建一个三角形。在度数 > 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());
}
另见 How to triangulate from a Voronoï diagram?有关该问题的更多背景信息。
关于c++ - 如何在 Boost 中对多边形进行三角剖分?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34342038/