Intersection of two simple CCW triangles polygons cause a precondition error

[RustyLooks]

I am trying the intersection of those two simple CCW triangles :

    double triangle1_data[3][2] = {{-970.617, 2590.618}, {6365.203, -5386.531}, {3072.988, 7034.1}};
    double triangle2_data[3][2] = {{7457.082, 553.771},{-989.492, 5886.865},{9653.454, -7686.112}};

And when running the code below where I create PolygonWithHoles with an exact predicates, inexact coordinates kernel (for fast computation, I don't want to use the exact coordinates kernel) I get the following precondition error:

terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: (m_traits.compare_y_at_x_2_object()(p, cv) == EQUAL) && compare_xy(cv.left(), p) == SMALLER && compare_xy(cv.right(), p) == LARGER
File: /usr/local/include/CGAL/Arr_segment_traits_2.h
Line: 609
Aborted

Considering the triangles are CCW, they are not degenerate and thus can't cause instability as stated in the documentation, I don't see why this precondition is triggered. If I use an exact coordinate kernel it works but then I get a 10x penalty on computing.

Here are the commands I ran, and the source code:

g++ -o main.cpp.o -c main.cpp 
g++ -o test main.cpp.o -lgmp
./test

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2.h>
#include <vector>
#include <iostream>

int main() {
    using CGALPolygon = CGAL::Polygon_2<CGAL::Exact_predicates_inexact_constructions_kernel>;
    using CGALPolygonWithHoles = CGAL::Polygon_with_holes_2<CGAL::Exact_predicates_inexact_constructions_kernel>;

    double triangle1_data[3][2] = {{-970.617, 2590.618}, {6365.203, -5386.531}, {3072.988, 7034.1}};
    double triangle2_data[3][2] = {{7457.082, 553.771},{-989.492, 5886.865},{9653.454, -7686.112}};
    CGALPolygon triangle1;
    for (const auto d: triangle1_data) {
        triangle1.push_back({d[0], d[1]});
    }
    CGALPolygonWithHoles t1(triangle1);
    CGALPolygon triangle2;
    for (const auto d: triangle2_data) {
        triangle2.push_back({d[0], d[1]});
    }
    CGALPolygonWithHoles t2(triangle2);

    std::vector<CGALPolygonWithHoles> out;
    CGAL::intersection(t1,t2, std::back_inserter(out));

    for (const auto p:out){
        std::cout<<p<<std::endl;
    }
    return 0;
}

Version of CGAL: 5.6 Git hash: de4fa0d7d57b5a997012f2804161386ff4bc0d0f

[sloriot]

Any reason not to use Triangle_2 type and intersection(Triangle_2, Triangle_2)?

[RustyLooks]

Any reason not to use Triangle_2 type and intersection(Triangle_2, Triangle_2)?

Yes this is a very simple example for more general intersection of polygons with hole (respecting all the preconditions listed in the documentation)

[sloriot]

You need to use CGAL::Exact_predicates_exact_constructions_kernel if you want to use the sweep-line based intersection computation.

https://www.cgal.org/FAQ.html#inexact_NT

[RustyLooks]

You need to use CGAL::Exact_predicates_exact_constructions_kernel if you want to use the sweep-line based intersection computation.

https://www.cgal.org/FAQ.html#inexact_NT

As explained in the issue, I know that it work with the exact construction kernel but the penalty is a 10x performance penalty

[RustyLooks]

If I am referring to: "If your program does not involve the construction of new objects from the input data (such as the intersection of two objects, or the center of a sphere defined by the input objects), the CGAL::Exact_predicates_inexact_constructions_kernel kernel provides a nice and fast way to use exact predicates together with an inexact number type such as double for constructions." the kernel I am using should support my very simple triangles with very normal coordinates.

I can even provide an example with integer Quad polygons that fails that precondition.

[sloriot]

If you know, then the title of your issue is misleading. Precondition is raised because exact constructions are required. Moreover, you are saying that you have a 10x penalty but you are compiling in "debug" mode as you have assertions.

[sloriot]

intersection points = new objects from input data