c++ - 使用 boost::polygon::voronoi 对点集进行三角剖分会导致三角形重叠

Question

我正在使用boost::polygon::voronoi下面的代码（在这个问题下找到）对一组 2d 点进行三角测量

boost::polygon::voronoi_diagram<vert_value_typed> vd{};
boost::polygon::construct_voronoi(vertices.begin(), vertices.end(), &vd);
for (const auto& vertex : vd.vertices()) {
    boost::container::static_vector<uint32_t, 40> big_face{};
    const auto* start_edge = vertex.incident_edge();
    auto* edge = start_edge;
    do {
        const auto cell = edge->cell();
        ASSERT(cell && cell->contains_point());
        big_face.push_back(util::checked_cast<uint32_t>(cell->source_index()));
        if (big_face.size() == 3) {
            // process output triangles
            faces.push_back({
                big_face[0],
                big_face[1],
                big_face[2]
            });
            big_face.erase(big_face.begin() + 1);
        }
        edge = edge->rot_next();
    } while (edge != start_edge);
}

但是，我的一些三角形重叠，如下图所示：

请注意，重叠的三角形与其他三角形相比总是具有反向剔除，即它们指向下方。

如何修改算法以使生成的网格不包含这些重叠图像？我对 voronoi 图不够流利，无法手动解决这个问题。

标签： c++triangulationvoronoiboost-polygon