c++ - 计算多边形 union 时在 CGAL 中触发的断言

Question

我正在用 Python 编写一个将水印应用于字体文件的应用程序。字形是带孔的非凸多边形，由 PostScript 中定义的贝塞尔样条曲线组成。水印需要与字形合并，而不是重叠。我无法在 Python 中找到一个库来执行此操作，所以我使用的是 CGAL 和 C++。我让它在大多数字形上都能很好地工作，但在其他字形上却神秘地失败了。

最初，我对 CGAL 印象深刻。它看起来非常全面和复杂，似乎提供了我需要的所有功能，但它存在一个致命缺陷——我几乎不敢相信——该库不包含错误处理。没有错误代码，没有异常，只有断言——但仅限于调试版本。在发布版本中，您会得到一个很好的段错误。此外，这些断言没有揭示问题的本质。

该程序仅在某些字形上失败。字母“e”工作正常，但它在“a”上崩溃。当我尝试计算字形与水印的 union 时，就会发生崩溃。 “a”字形没有明显的错误。我的应用程序正确解析 PostScript 并在 QGraphicsView 上很好地呈现它。

该程序需要在服务器上运行，并将其输出直接发送给客户，因此它必须是可靠的。我无法从断言失败或段错误中恢复，那我该怎么办？

即使我让它可靠地工作，我怎么能相信它永远不会失败？如果有某种错误处理，我可以跳过它失败的几个字形，让它们不加水印——不理想，但可以接受。我只是不明白这个图书馆的作者在想什么；他们付出了巨大的努力来提供最全面的几何库，只是为了确保它完全不适合目的。

目前，看起来我必须自己修改代码才能以合理的方式处理错误，但这似乎太荒谬了。

如果我表现得不耐烦，我很抱歉，但我已经过了最后期限，我的客户不会关心或理解这些借口。

断言失败发生在 multiset.h 的第 2141 行:

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

当我在 BezierPolygonSet 上调用 join() 时会发生这种情况。我的类型如下:

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;

任何帮助将非常感激。谢谢。

编辑:

我有一个名为 Geometry 的模块，它包装了 CGAL 代码并公开了一堆几何图元(Point、Curve、LineSegment、CubicBezier、Path)和函数:

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

Path 类有一个名为 computeUnion 的方法，如下所示:

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);
}

当我调用 join() 时发生错误。多边形是从如下路径创建的:

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;
}

请注意，我通过将曲线 n+1 的第一个点设置为曲线 n 的最后一个点来确保多边形边界没有间隙，以防它们略有不同。我希望这能解决问题，但事实并非如此。我想不出任何其他可能使形状无效的事情。

这是“e”字形与水印(一个 X)的成功合并。


这是“a”字形的样子。此字形上的合并失败。


编辑2:

这是从 PostScript 解析后构成“a”字形的曲线。它似乎没有任何问题。正如我所说，渲染时看起来不错。该错误可能发生在从该数据转换为 CGAL 类型的过程中。线段被转换为具有 2 个控制点的 BezierCurves。我会进一步调查。

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)]

编辑 3:

这是转换为 CGAL 曲线后的“a”字形曲线。请注意，它们与平移前的曲线完全匹配，这意味着它们中的任何一条都不必拆分为 X 单调子曲线；它们一定已经是 X-monotone 了。

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

此多边形在添加到 BezierPolygonSet 时会导致断言失败。有任何想法吗？

Answer 1

您可以自定义错误处理；见manual .

请附上完整的独立程序。您列出的陈述对我来说没有任何问题。

您可以使用折线近似贝塞尔曲线，并使用折线处理整个事物。如果问题在于贝塞尔曲线的处理，那么这将解决它。如果这是可以接受的，它也会更有效率。

我们更正了处理贝塞尔曲线的 CGAL 组件中的一个错误，即 Arr_Bezier_curve_traits_2.h .