Assertion violation Segment_Delaunay_graph_2 inexact constructions

[Yvee1]

Issue Details

For certain input, the insert function of Segment_Delaunay_graph_2 throws an assertion violation error (inexact constructions).

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/Segment_Delaunay_graph_adaptation_traits_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel    K;
typedef CGAL::Segment_Delaunay_graph_traits_2<K>               Gt;
typedef CGAL::Segment_Delaunay_graph_2<Gt>                     SDG2;
typedef CGAL::Segment_Delaunay_graph_adaptation_traits_2<SDG2> AT;
typedef AT::Site_2                                             Site;

int main() {
    std::vector<CGAL::Point_2<K>> points;

    points.emplace_back(379.64508315, 597.52865773999997);
    points.emplace_back(379.55375268, 598.72069828999997);
    points.emplace_back(379.46242221, 599.91273883999997);
    points.emplace_back(379.65931647000002, 601.10477938999998);
    points.emplace_back(379.85739683999998, 601.73934823999991);

    SDG2 delaunay;
    for (int i = 0; i < points.size()-1; i++) {
        auto site = Site::construct_site_2(points[i], points[i+1]);
        delaunay.insert(site);
    }

    return 0;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): WSL2 on Windows 11, 64 bits
• Compiler: g++
• Release or debug mode: Debug mode
• CGAL version: 5.4-1
• Boost version: 1.74.0

[albert-github]

for (int i = 0; i < points.size()-1; i++)

shouldn't this be:

for (int i = 0; i < points.size()-2; i++)

as otherwise points[i+1] will be out of range?

[Yvee1]

I already compensate for the i+1 indexing by subtracting one from the size; if you would just loop over the points you would do for (int i = 0; i < points.size(); i++).

[albert-github]

OK yes correct.

[afabri]

The exact predicates kernel does not provide all predicates needed by the Segment_Delaunay_graph_2. So you have to use the filterered traits class: typedef CGAL::Segment_Delaunay_graph_filtered_traits_2 K, CGAL::Field_with_sqrt_tag> Gt;

[Yvee1]

Thanks, that works. I suppose it was my mistake then and the issue can be closed. I do think the assertion error is misleading for the user. It may be worth improving the 'error message' if it is not too much work.

[MaelRL]

It's difficult to detect in the code, because we do not want to prevent some geometric traits combinations for advanced users.

Note that you might also be interested in using Segment_Delaunay_graph_filtered_traits_without_intersections_2, if you don't have intersection between segments of your input.