Arrangement insert throws bad_get

[Yvee1]

Issue Details

I am using the arrangements package to create an arrangement of two closed polycurves consisting of circular arcs. In some cases it throws the following exception on insertion of the polycurves using CGAL::insert.

terminate called after throwing an instance of 'boost::wrapexcept<boost::bad_get>'
  what():  boost::bad_get: failed value get using boost::get

The polycurves in question in image form.

Their edges overlap:

The polycurves are well-oriented and continuous. They are self-intersecting (that is, they have identical start and end points) but this is allowed according to the documentation.

Source Code

Here is code to reproduce the issue.

header main.h

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Circle_2.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_circle_segment_traits_2.h>
#include <CGAL/Arr_conic_traits_2.h>
#include <CGAL/CORE_algebraic_number_traits.h>
#include <CGAL/Gps_traits_2.h>
#include <CGAL/Gps_circle_segment_traits_2.h>
#include <CGAL/Arr_polycurve_traits_2.h>

typedef CGAL::Epeck Exact;
typedef CGAL::Arr_circle_segment_traits_2<Exact> CSTraits;
typedef CGAL::Gps_circle_segment_traits_2<Exact> CSTraitsBoolean;
typedef CGAL::Arr_polycurve_traits_2<CSTraits> PolyCSTraits;
typedef CSTraitsBoolean::Polygon_2 CSPolygon;
typedef PolyCSTraits::Curve_2 CSPolycurve;
typedef CGAL::Arrangement_2<CSTraits> CSArrangement;
typedef CSTraits::X_monotone_curve_2 X_monotone_curve_2;
typedef CSTraits::Curve_2 Curve_2;
typedef CSTraits::Point_2 OneRootPoint;
typedef CGAL::Circle_2<Exact> Circle;

template <class Traits, class Ccb>
CGAL::General_polygon_2<Traits> ccb_to_polygon(Ccb ccb) {
    auto curr = ccb;

    std::vector<typename Traits::X_monotone_curve_2> x_monotone_curves;
    do {
        auto curve = curr->curve();
        if (curr->source()->point() == curve.source()) {
            x_monotone_curves.push_back(curve);
        } else {
            Traits traits;
            auto opposite = traits.construct_opposite_2_object();
            x_monotone_curves.push_back(opposite(curve));
        }
    } while(++curr != ccb);

    return {x_monotone_curves.begin(), x_monotone_curves.end()};
}

Curve_2 toCurve(const X_monotone_curve_2& xmc);

template <class InputIterator>
CSPolycurve arrPolycurveFromXMCurves(InputIterator begin, InputIterator end) {
    PolyCSTraits traits;
    auto construct = traits.construct_curve_2_object();
    std::vector<Curve_2> curves;
    std::transform(begin, end, std::back_inserter(curves), [](const X_monotone_curve_2& xm_curve) {
        return toCurve(xm_curve);
    });
    return construct(curves.begin(), curves.end());
}

CSPolycurve arrPolycurveFromCSPolygon(const CSPolygon& polygon);

source main.cpp

#include "main.h"

CSPolycurve arrPolycurveFromCSPolygon(const CSPolygon& polygon) {
    return arrPolycurveFromXMCurves(polygon.curves_begin(), polygon.curves_end());
}

Curve_2 toCurve(const X_monotone_curve_2& xmc) {
    if (xmc.is_linear()) {
        return {xmc.supporting_line(), xmc.source(), xmc.target()};
    } else if (xmc.is_circular()) {
        return {xmc.supporting_circle(), xmc.source(), xmc.target()};
    } else {
        throw std::runtime_error("Impossible: circle-segment x-monotone curve is neither linear nor circular.");
    }
}

int main() {
    auto r = 5.204 * 3;
    auto r_ = 5.204 * 3 * 0.675;
    auto r2 = r * r;
    auto r2_ = r_ * r_;
    Circle c1({2597.9, -364.3}, r2, CGAL::CLOCKWISE);
    Circle c2({2609.2, -342.6}, r2, CGAL::CLOCKWISE);
    Circle c2_({2609.2, -342.6}, r2_, CGAL::CLOCKWISE);

    auto getIntersections = [](const Circle& one, const Circle& two) {
        CSArrangement arr;
        CGAL::insert(arr, one);
        CGAL::insert(arr, two);
        std::vector<OneRootPoint> intersectionPoints;
        for (auto vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
            if (vit->degree() == 4) {
                intersectionPoints.push_back(vit->point());
            }
        }
        std::sort(intersectionPoints.begin(), intersectionPoints.end(), [](const OneRootPoint& p1, const OneRootPoint& p2) { return p1.x() < p2.x(); });
        assert(intersectionPoints.size() == 2);
        return intersectionPoints;
    };

    auto isp12 = getIntersections(c1, c2);

    X_monotone_curve_2 arc1(c1, isp12[0], isp12[1], c1.orientation());
    X_monotone_curve_2 arc2(c2, isp12[1], isp12[0], c2.orientation());
    std::vector<X_monotone_curve_2> pgnArcs({arc1, arc2});
    std::vector<Curve_2> pgnArcsCurves({toCurve(arc1), toCurve(arc2)});

    CSArrangement arr;
    CGAL::insert(arr, c1);
    CGAL::insert(arr, c2);
    CGAL::insert(arr, c2_);

    CSArrangement::Face_handle fh;
    for (auto eit = arr.halfedges_begin(); eit != arr.halfedges_end(); ++eit) {
        if (eit->source()->point() == isp12[0]) {
            fh = eit->face();
        }
    }

    CSPolygon pgn(pgnArcs.begin(), pgnArcs.end());

    auto plnPoly = ccb_to_polygon<CSTraits>(fh->outer_ccb());
    CSPolygon pln(plnPoly.curves_begin(), plnPoly.curves_end());
    using Arr = CGAL::Arrangement_2<PolyCSTraits>;
    Arr curveArr;
    auto plnPolycurve = arrPolycurveFromCSPolygon(pln);
    auto pgnPolyCurve = arrPolycurveFromCSPolygon(pgn);
    std::cout << "Pln curves" << std::endl;
    for (auto cit = plnPolycurve.subcurves_begin(); cit != plnPolycurve.subcurves_end(); ++cit) {
        std::cout << cit->source() << " -> " << cit->target() << std::endl;
    }
    std::cout << "Pgn curves" << std::endl;
    for (auto cit = pgnPolyCurve.subcurves_begin(); cit != pgnPolyCurve.subcurves_end(); ++cit) {
        std::cout << cit->source() << " -> " << cit->target() << std::endl;
    }
    CGAL::insert(curveArr, pgnPolyCurve);
    CGAL::insert(curveArr, plnPolycurve);
}

Environment

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

[afabri]

Let me confirm that we also have the problem in the master branch.

[efifogel]

It's a bug. This is a slightly more simple program that reproduces it: steven.cpp.tar.gz The bug occurs when inserting 2 poly-circular-arcs that partially overlap. The first consists of one arc (red) and the second consists of 2 arcs (green). It works fine when inserting the (three) individual circular arcs.