CGAL users discussion list

[Forest Darling <>]

Hello,

As I mentioned in my earlier email, I am having a discrepancy between the exact math and floating point kernels when constructing a "CGAL::Gps_circle_segment_traits_2" Polygon_2, resulting in a crash.

I attached an image of the test case, and the C++ sourcecode that constructs the Polygon_2 and tries to calculate it's orientation. You can uncomment the "#define USE_EXACT_MATH" on line 3 of main.cpp to enable the use of the exact construction kernel to verify it works under that.

Console output when using the "CGAL::Exact_predicates_exact_constructions_kernel" kernel:

g++ -c -o main.o main.cpp -Os -g -std=c++1z -DCGAL_DISABLE_ROUNDING_MATH_CHECK=ON
g++ -o broken-cgal main.o -lCGAL -lCGAL_Core -lmpfr -lgmp
poly = 6 (0 0.5 0.0001 1) [0.01 0.5 --> 0.01 0.5] (0 0.5 0.0001 1) [0.01 0.5 --> -0.01 0.5] (0 0.5 0.0001 1) [-0.01 0.5 --> -0.01 0.5] [-0.01 0.5 --> -0.01 0] (0 0 0.0001 1) [-0.01 0 --> 0.01 0] [0.01 0 --> 0.01 0.5]
poly.orientation() = 1

Console output when using the "CGAL::Simple_cartesian<double>" kernel:

g++ -c -o main.o main.cpp -Os -g -std=c++1z -DCGAL_DISABLE_ROUNDING_MATH_CHECK=ON
g++ -o broken-cgal main.o -lCGAL -lCGAL_Core -lmpfr -lgmp
poly = 4 (0 0.5 0.0001 1) [0.01 0.5 --> -0.01 0.5] [-0.01 0.5 --> -0.01 0] (0 0 0.0001 1) [-0.01 0 --> 0.01 0] [0.01 0 --> 0.01 0.5]
terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: cv1.point_position (p) == EQUAL && cv2.point_position (p) == EQUAL
File: /usr/include/CGAL/Arr_circle_segment_traits_2.h
Line: 254
Aborted (core dumped)

I am using "stock" CGAL 4.11-2build1 on Ubuntu 18.04 64-bit.

Is it normal for the algorithms to be this sensitive? Is it a bug? Or am I doing something wrong?

I'd appreciate any insight!

--Forest

Attachment: Makefile
Description: Binary data

#include <iostream>

// #define USE_EXACT_MATH

#ifdef USE_EXACT_MATH
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#else // !defined(USE_EXACT_MATH)
#include <CGAL/Simple_cartesian.h>
#endif // USE_EXACT_MATH

#include <CGAL/Gps_circle_segment_traits_2.h>
#include <CGAL/General_polygon_set_2.h>
#include <CGAL/General_polygon_2.h>

#ifdef USE_EXACT_MATH
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
#else // !defined(USE_EXACT_MATH)
typedef CGAL::Simple_cartesian<double> Kernel;
#endif // USE_EXACT_MATH

typedef Kernel::Point_2                                   Point_2;
typedef Kernel::Circle_2                                  Circle_2;
typedef Kernel::Line_2                                    Line_2;
typedef CGAL::Gps_circle_segment_traits_2<Kernel>         Traits_2;
typedef CGAL::General_polygon_set_2<Traits_2>             Polygon_set_2;
typedef Traits_2::Polygon_2                               Polygon_2;
typedef Traits_2::Polygon_with_holes_2                    Polygon_with_holes_2;
typedef Traits_2::Curve_2                                 Curve_2;
typedef Traits_2::X_monotone_curve_2                      X_monotone_curve_2;

// forward declarations
static void AddLine(Polygon_2 &poly, const Point_2 &pt1, const Point_2 &pt2);
static void AddArc(Polygon_2 &poly, const Point_2 &pt1, const Point_2 &pt2, const Point_2 &pt3);

int main(int argc, char **argv)
{
    Polygon_2 poly;
    AddArc (poly, Point_2( 0.01, 0.5), Point_2(-0.01, 0.5), Point_2(0,  0.51));
    AddLine(poly, Point_2(-0.01, 0.5), Point_2(-0.01, 0.0));
    AddArc (poly, Point_2(-0.01, 0.0), Point_2( 0.01, 0.0),  Point_2(0, -0.01));
    AddLine(poly, Point_2( 0.01, 0.0), Point_2( 0.01, 0.5));

    // this builds the following test case
    // 4 (0 0.5 0.0001 1) [0.01 0.5 --> -0.01 0.5] [-0.01 0.5 --> -0.01 0] (0 0 0.0001 1) [-0.01 0 --> 0.01 0] [0.01 0 --> 0.01 0.5]

    std::cout << "poly = " << poly << std::endl;
    
    // the call to Polygon_2::orientation() will fail
    // (if not using exact math) with this error message:
/*
terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: cv1.point_position (p) == EQUAL && cv2.point_position (p) == EQUAL
File: /usr/include/CGAL/Arr_circle_segment_traits_2.h
Line: 254
Aborted (core dumped)
*/
    const int orient = poly.orientation();
    std::cout << "poly.orientation() = " << orient << std::endl;

// gdb backtrace:
/*
CGAL::precondition_fail(char const*, char const*, int, char const*) () from /usr/lib/x86_64-linux-gnu/libCGAL.so.13
CGAL::Arr_circle_segment_traits_2<CGAL::Simple_cartesian<double>, true>::Compare_y_at_x_right_2::operator() (this=<optimized out>, cv1=..., cv2=..., p=...) at /usr/include/CGAL/Arr_circle_segment_traits_2.h:259
CGAL::Gps_traits_adaptor<CGAL::Arr_circle_segment_traits_2<CGAL::Simple_cartesian<double>, true> >::Orientation_2::operator()<std::_List_const_iterator<CGAL::_X_monotone_circle_segment_2<CGAL::Simple_cartesian<double>, true> > > (
    this=<optimized out>, begin=..., end=...) at /usr/include/CGAL/Boolean_set_operations_2/Gps_traits_adaptor.h:166
CGAL::General_polygon_2<CGAL::Arr_circle_segment_traits_2<CGAL::Simple_cartesian<double>, true> >::orientation (this=0x7fffffffdf00) at /usr/include/CGAL/General_polygon_2.h:119
main (argc=<optimized out>, argv=<optimized out>) at main.cpp:58
*/

    return 0;
}

static void AddLine(Polygon_2 &poly, const Point_2 &pt1, const Point_2 &pt2)
{
    Traits_2 traits;
    std::list<CGAL::Object> objects;
    // NOTE: CGAL doesn't like zero-length lines!
    if (pt1 != pt2)
    {
        Curve_2 curve(pt1, pt2);
        traits.make_x_monotone_2_object() (curve, std::back_inserter(objects));
    }
    else
    {
        std::cerr << "WARNING: zero length line segment!" << std::endl;
    }
    // Construct the polygon.
    X_monotone_curve_2 arc;
    std::list<CGAL::Object>::iterator iter;
    for (iter = objects.begin(); iter != objects.end(); ++iter)
    {
        CGAL::assign(arc, *iter);
        poly.push_back(arc);
    }
}

static void AddArc(Polygon_2 &poly, const Point_2 &pt1, const Point_2 &pt2, const Point_2 &pt3)
{
    Traits_2 traits;
    std::list<CGAL::Object> objects;
    Curve_2 curve(pt1, pt3, pt2);
    if (pt1 != pt2)
    {
        traits.make_x_monotone_2_object() (curve, std::back_inserter(objects));
    }
    else
    {
        std::cerr << "WARNING: zero length arc segment!" << std::endl;
    }
    X_monotone_curve_2 arc;
    std::list<CGAL::Object>::iterator iter;
    for (iter = objects.begin(); iter != objects.end(); ++iter)
    {
        CGAL::assign(arc, *iter);
        poly.push_back(arc);
    }
}

Attachment: CGAL_Test_Shape.png
Description: PNG image