0

I'm triangulating a set of 2d points using boost::polygon::voronoi and the code below (found under this question)

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

However, some of my triangles overlap as illustrated by the following image:

Image of resulting triangles Note that the overlapping triangles always have a reversed culling compared to the rest, i.e they are pointing downwards.

How can I modify the algorithm so that the resulting mesh does not contain these overlapping images? I'm not fluent enough in voronoi diagrams to solve this manually.

Viktor Sehr
  • 12,825
  • 5
  • 58
  • 90
  • It looks like you added random heights to the 2D points, and the overlap is just caused by the 3D projection. Are the triangles still overlapping if you view the mesh from directly above? – G. Sliepen Sep 04 '19 at 17:08
  • @G.Sliepen: Yes they are overlapping, there is no random height in the image. – Viktor Sehr Sep 04 '19 at 17:15

0 Answers0