cgal

cgal copied to clipboard

Issue Details

I encounter a rare case where the removal of a point vertex in the Segment Delaunay graph fails unexpectedly. I ensure that no there are no incident segments.

I have included an isolated example below. First the instance looks like this:

The three polylines are disjoint (zoomed in on the almost-intersection):

Then I first remove two segments and a point of the middle polyline, which works fine:

However removal of the middle now isolated point vertex fails.

Source Code

#include <CGAL/predicates/sign_of_determinant.h>
#include <CGAL/Segment_Delaunay_graph_2.h>
#include <CGAL/Segment_Delaunay_graph_traits_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel    K;
typedef CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K, CGAL::Field_with_sqrt_tag>  Gt;
typedef CGAL::Segment_Delaunay_graph_2<Gt>                     SDG2;

int main() {
    std::vector<CGAL::Point_2<K>> points1;
    std::vector<CGAL::Point_2<K>> points2;
    std::vector<CGAL::Point_2<K>> points3;

    points1.emplace_back(22.3969, 94.1914);
    points1.emplace_back(23.6548, 96.6021);
    points1.emplace_back(27.8419, 94.5151);
    points1.emplace_back(26.7312, 88.9916);

    points2.emplace_back(22.1502, 94.4831);
    Gt::Point_2 s(23.9491, 97.2822);
    points2.push_back(s);
    Gt::Point_2 t(26.2174, 95.7656);
    points2.push_back(t);
    Gt::Point_2 u(26.7982, 96.4668);
    points2.push_back(u);
    Gt::Point_2 v(29.5491, 101.4);
    points2.push_back(v);

    points3.emplace_back(21.6136, 94.8987);
    points3.emplace_back(24.3992, 97.7507);
    points3.emplace_back(25.8233, 101.603);

    SDG2 delaunay;
    auto insert_polyline = [&delaunay](const std::vector<Gt::Point_2>& pts) {
        std::vector<Gt::Segment_2> segments;
        for (int i = 0; i < pts.size()-1; i++) {
            segments.emplace_back(pts[i], pts[i+1]);
        }
        delaunay.insert_segments(segments.begin(), segments.end());
    };
    insert_polyline(points1);
    insert_polyline(points2);
    insert_polyline(points3);

    std::unordered_map<Gt::Point_2, SDG2::Vertex_handle> p_vertex;
    std::unordered_map<Gt::Segment_2, SDG2::Vertex_handle> e_vertex;

    for (auto vit = delaunay.finite_vertices_begin(); vit != delaunay.finite_vertices_end(); vit++) {
        auto site = vit->site();
        if (site.is_point()) {
            p_vertex[site.point()] = vit;
        } else {
            e_vertex[site.segment()] = vit;
        }
    }

    Gt::Segment_2 st(s, t);
    Gt::Segment_2 tu(t, u);
    Gt::Segment_2 uv(u, v);
    std::cout << "Removing: " << tu << std::endl;
    std::cout << delaunay.remove(e_vertex.at(tu)) << std::endl;
    std::cout << "Removing: " << st << std::endl;
    std::cout << delaunay.remove(e_vertex.at(st)) << std::endl;
    std::cout << "Removing: " << uv << std::endl;
    std::cout << delaunay.remove(e_vertex.at(uv)) << std::endl;
    std::cout << "Removing: " << t << std::endl;
    std::cout << delaunay.remove(p_vertex.at(t)) << std::endl;
    std::cout << "Removing: " << u << std::endl;
    std::cout << delaunay.remove(p_vertex.at(u)) << std::endl;

    return 0;
}

The last remove return value is false.