Assertion triggered in CGAL when computing polygon union

Question

I'm writing an application in Python that applies a watermark to a font file. The glyphs are non-convex polygons with holes and consist of bezier splines defined in PostScript. The watermark needs to merge with the glyphs, not overlap. I was unable to find a library to do this in Python so I'm using CGAL & C++. I have it working nicely on most glyphs, but it's mysteriously failing on others.

Initially, I was very impressed with CGAL. It looked very comprehensive and sophisticated and seemed to provide all the functionality I needed, but it suffers one fatal flaw - and I almost can't believe it - the library contains no error handling. No error codes, no exceptions, just assertions - but only in the debug build. In the release build you get a nice segmentation fault instead. Furthermore, the assertions reveal nothing about the nature of the problem.

The program fails only on certain glyphs. The letter 'e' works fine, but it crashes on 'a'. The crash occurs when I attempt to compute the union of the glyph with the watermark. There is nothing visibly wrong with the 'a' glyph. My application parses the PostScript correctly and renders it fine on a QGraphicsView.

This program needs to run on a server and its output sent directly to the customer so it must be reliable. I can't recover from an assertion failure or a segfault, so what can I do?

Even if I get it working reliably, how can I trust that it will never fail? If there was some kind of error handling in place, I could just skip the few glyphs that it fails on, leaving them unwatermarked - not ideal, but acceptable. I just don't understand what the authors of this library were thinking; they went to such tremendous effort to make the most comprehensive geometry library available only to ensure that it's completely unfit for purpose.

Currently, it's looking like I'm going to have to modify the code myself to handle the error in a sensible way, but this just seems so ridiculous.

I'm sorry if I come off as impatient, but I'm way past my deadline and my client isn't going to care about or understand these excuses.

The assertion failure is occurring on line 2141 of multiset.h:

CGAL_multiset_precondition (comp_f(object, nodeP->object) != LARGER);

It happens when I call join() on a BezierPolygonSet. My types are as follows:

typedef CGAL::CORE_algebraic_number_traits NtTraits;
typedef NtTraits::Rational Rational;
typedef NtTraits::Algebraic Algebraic;

typedef CGAL::Cartesian<Rational> RatKernel;
typedef CGAL::Cartesian<Algebraic> AlgKernel;

typedef RatKernel::Point_2 BezierRatPoint;

typedef CGAL::Arr_Bezier_curve_traits_2<RatKernel, AlgKernel, NtTraits> Traits;

typedef Traits::Point_2 BezierPoint;
typedef Traits::Curve_2 BezierCurve;

typedef CGAL::Gps_traits_2<Traits> BezierTraits;

typedef BezierTraits::X_monotone_curve_2 BezierXMonotoneCurve;
typedef BezierTraits::General_polygon_2 BezierPolygon;
typedef BezierTraits::General_polygon_with_holes_2 BezierPolygonWithHoles;
typedef CGAL::Gps_default_dcel<BezierTraits> BezierDcelTraits;
typedef CGAL::General_polygon_set_2<BezierTraits, BezierDcelTraits> BezierPolygonSet;

Any help would be much appreciated. Thanks.

EDIT:

I have a module called Geometry which wraps the CGAL code and exposes a bunch of geometric primitives (Point, Curve, LineSegment, CubicBezier, Path) and the functions:

PathList toPathList(const PolyList& polyList);
PolyList toPolyList(const PathList& paths);

The Path class has a method called computeUnion, which looks like this:

PathList Path::computeUnion(const PathList& paths1, const PathList& paths2) {
    PolyList polyList1 = toPolyList(paths1);
    PolyList polyList2 = toPolyList(paths2);

    cgal_wrap::BezierPolygonSet polySet;

    for (auto i : polyList1) {
        polySet.join(i);
    }

    for (auto i : polyList2) {
        polySet.join(i);
    }

    PolyList polyList;
    polySet.polygons_with_holes(std::back_inserter(polyList));

    return toPathList(polyList);
}

The error occurs when I call join(). The polygons are created from paths like so:

PolyList toPolyList(const PathList& paths) {
    cgal_wrap::Traits traits;
    cgal_wrap::Traits::Make_x_monotone_2 fnMakeXMonotone = traits.make_x_monotone_2_object();

    cgal_wrap::RatKernel ratKernel;
    cgal_wrap::RatKernel::Equal_2 fnEqual = ratKernel.equal_2_object();

    PolyList polyList; // The final polygons with holes
    cgal_wrap::BezierPolygon outerPoly;
    std::list<cgal_wrap::BezierPolygon> holes;
    std::list<cgal_wrap::BezierXMonotoneCurve> monoCurves;
    bool first = true;
    cgal_wrap::BezierRatPoint firstPoint;

    // For each path in the list
    for (auto i = paths.begin(); i != paths.end(); ++i) {
        const Path& path = *i;

        cgal_wrap::BezierRatPoint prevEndPoint;

        // For each curve in the path
        for (auto j = path.begin(); j != path.end(); ++j) {
            const Curve& curve = **j;

            std::list<cgal_wrap::BezierRatPoint> points;

            if (curve.type() == LineSegment::type) {
                const LineSegment& lseg = dynamic_cast<const LineSegment&>(curve);

                cgal_wrap::BezierRatPoint A = lseg.A();

                if (j != path.begin()) {
                    if (A != prevEndPoint) {
                        // TODO
                        assert(false);
                    }

                    A = prevEndPoint;
                }

                points.push_back(cgal_wrap::BezierRatPoint(A));
                points.push_back(cgal_wrap::BezierRatPoint(lseg.B()));
            }
            else if (curve.type() == CubicBezier::type) {
                const CubicBezier& bezier = dynamic_cast<const CubicBezier&>(curve);

                cgal_wrap::BezierRatPoint A = bezier.A();

                if (j != path.begin()) {
                    if (A != prevEndPoint) {
                        // TODO
                        assert(false);
                    }

                    A = prevEndPoint;
                }

                points.push_back(cgal_wrap::BezierRatPoint(A));
                points.push_back(cgal_wrap::BezierRatPoint(bezier.B()));
                points.push_back(cgal_wrap::BezierRatPoint(bezier.C()));
                points.push_back(cgal_wrap::BezierRatPoint(bezier.D()));
            }

            bool bClosesCurve = false;

            if (!first && Point(points.back()) == Point(firstPoint)) {
                points.pop_back();
                points.push_back(firstPoint);
                bClosesCurve = true;
            }

            prevEndPoint = points.back();

            cgal_wrap::BezierCurve cgalCurve(points.begin(), points.end());
            std::list<CGAL::Object> monoObjs;
            fnMakeXMonotone(cgalCurve, std::back_inserter(monoObjs));

            // Append the x-monotone curves to the list
            cgal_wrap::BezierXMonotoneCurve monoCurve;
            for (auto o = monoObjs.begin(); o != monoObjs.end(); ++o) {
                if (CGAL::assign(monoCurve, *o)) {
                    monoCurves.push_back(monoCurve);
                }
            }

            if (!first) {
                // If this curve closes the current chain, thereby creating a new polygon
                if (bClosesCurve) {

                    // Add the new polygon to the list

                    cgal_wrap::BezierPolygon subPoly(monoCurves.begin(), monoCurves.end());

                    if (subPoly.orientation() == CGAL::COUNTERCLOCKWISE) {
                        if (!outerPoly.is_empty()) {
                            polyList.push_back(cgal_wrap::BezierPolygonWithHoles(outerPoly, holes.begin(), holes.end()));
                            holes.clear();
                        }

                        outerPoly = subPoly;
                    }
                    else {
                        holes.push_back(subPoly);
                    }

                    monoCurves.clear();
                    first = true;
                }
            }
            else {
                // This is the first curve in the chain - store its source point
                firstPoint = cgalCurve.control_point(0);
                first = false;
            }
        }
    }

    polyList.push_back(cgal_wrap::BezierPolygonWithHoles(outerPoly, holes.begin(), holes.end()));

    return polyList;
}

Notice that I'm careful to ensure that the polygon boundaries have no gaps by setting the first point of curve n+1 to the last point of curve n in case they were slightly different. I was hoping this would solve the problem, but it didn't. I can't think of any other things that might make the shapes invalid.

Here is the successful merging of the 'e' glyph with the watermark (an X).

Here is what the 'a' glyph looks like. The merging fails on this glyph.

EDIT 2:

Here are the curves that make up the 'a' glyph after parsing it from PostScript. There doesn't appear to be anything wrong with it. As I said, it looks okay when rendered. The error probably occurs during the translation from this data into the CGAL types. The line segments get translated into BezierCurves with 2 control points. I will investigate further.

LineSegment[(344, 0), (409, 0)]
CubicBezier[(409, 0), (403, 24), (400, 68), (400, 161)]
LineSegment[(400, 161), (400, 324)]
CubicBezier[(400, 324), (400, 437), (330, 485), (232, 485)]
CubicBezier[(232, 485), (180, 485), (121, 472), (66, 437)]
LineSegment[(66, 437), (94, 385)]
CubicBezier[(94, 385), (127, 405), (167, 424), (224, 424)]
CubicBezier[(224, 424), (283, 424), (326, 392), (326, 320)]
LineSegment[(326, 320), (326, 290)]
LineSegment[(326, 290), (236, 287)]
CubicBezier[(236, 287), (188, 285), (150, 280), (118, 264)]
CubicBezier[(118, 264), (70, 242), (38, 199), (38, 136)]
CubicBezier[(38, 136), (38, 45), (102, -10), (188, -10)]
CubicBezier[(188, -10), (247, -10), (293, 18), (330, 53)]
LineSegment[(330, 53), (344, 0)]
LineSegment[(326, 234), (326, 114)]
CubicBezier[(326, 114), (304, 91), (260, 52), (201, 52)]
CubicBezier[(201, 52), (147, 52), (113, 88), (113, 140)]
CubicBezier[(113, 140), (113, 171), (127, 198), (154, 213)]
CubicBezier[(154, 213), (175, 224), (202, 230), (243, 231)]
LineSegment[(243, 231), (326, 234)]

EDIT 3:

Here are the 'a' glyph curves after translation into CGAL curves. Notice that they exactly match the curves before translation implying that none of them had to be split into X-monotone subcurves; they must have all been X-monotone already.

Outer boundary:
2  344 0  409 0 [1] | 344 0 --> 409 0
4  409 0  403 24  400 68  400 161 [1] | 409 0 --> 400 161
2  400 161  400 324 [1] | 400 161 --> 400 324
4  400 324  400 437  330 485  232 485 [1] | 400 324 --> 232 485
4  232 485  180 485  121 472  66 437 [1] | 232 485 --> 66 437
2  66 437  94 385 [1] | 66 437 --> 94 385
4  94 385  127 405  167 424  224 424 [1] | 94 385 --> 224 424
4  224 424  283 424  326 392  326 320 [1] | 224 424 --> 326 320
2  326 320  326 290 [1] | 326 320 --> 326 290
2  326 290  236 287 [1] | 326 290 --> 236 287
4  236 287  188 285  150 280  118 264 [1] | 236 287 --> 118 264
4  118 264  70 242  38 199  38 136 [1] | 118 264 --> 38 136
4  38 136  38 45  102 -10  188 -10 [1] | 38 136 --> 188 -10
4  188 -10  247 -10  293 18  330 53 [1] | 188 -10 --> 330 53
2  330 53  344 0 [1] | 330 53 --> 344 0
Holes:
Hole:
2  326 234  326 114 [1] | 326 234 --> 326 114
4  326 114  304 91  260 52  201 52 [1] | 326 114 --> 201 52
4  201 52  147 52  113 88  113 140 [1] | 201 52 --> 113 140
4  113 140  113 171  127 198  154 213 [1] | 113 140 --> 154 213
4  154 213  175 224  202 230  243 231 [1] | 154 213 --> 243 231
2  243 231  326 234 [1] | 243 231 --> 326 234

This polygon causes the assertion failure when added to a BezierPolygonSet. Any ideas?

Answer 1

1. You can customize error handling; see the manual.
2. Please attach a complete standalone program. Nothing looks wrong to me with statements you listed.

You can approximate the Bezier curves with polylines and process the whole things using polylines. If the problem is with the handling of Bezier curves, then this would solve it. If this is acceptable, it will also be more efficient.

We have fixed a bug in the CGAL component that handles Bezier curves, namely, Arr_Bezier_curve_traits_2.h.