cgal

cgal copied to clipboard

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

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?

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++).

OK yes correct.

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;

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.

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.