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.

[efifogel]

I've fixed the bug. The new code resides in the rep. Aos_2-polycurve-efif in my remote @.***:efifogel/cgal.git). I'll test it a bit further before I file a PR. I can tell you that the code that handled intersections in the polycurve traits was developed only with polylines (piecewise linear x-monotone curves) in mind. The new code supports all types of x-monotone curves.

---

/_____/) o /_________ __ // (____ ( ( ( (/ (/-(-'_(/ _/

On Mon, 30 Sept 2024 at 19:03, Andreas Fabri @.***> wrote:

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

— Reply to this email directly, view it on GitHub https://github.com/CGAL/cgal/issues/8468#issuecomment-2383603658, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABVBNOD7R7QS4POETWJKFOTZZFY45AVCNFSM6AAAAABN3J4HUWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGOBTGYYDGNRVHA . You are receiving this because you were assigned.Message ID: @.***>

[Yvee1]

Nice, thanks for looking into this!

[Yvee1]

Hi @lrineau, I see that the PR by Efi was closed but not merged. For me and for future reference, could you perhaps add a comment on how this issue has been fixed?

[lrineau]

Hi @Yvee1. You are right there is something fishy. @sloriot, can you please detail what you did about https://github.com/CGAL/cgal/pull/8525? I have assumed you merged it somehow, maybe using a cherry-pick or a rebase. Is that right?

[sloriot]

I have no idea what happened. I never saw the PR, so it was never tested. It will be tested tonight