问计算多边形并时在CGAL中触发的断言
EN

Stack Overflow用户

提问于 2016-01-02 13:27:19

回答 1查看 395关注 0票数 1

我正在用Python编写一个将水印应用于字体文件的应用程序。这些图形是带有孔的非凸多边形，由PostScript中定义的bezier样条组成.水印需要与符号合并，而不是重叠。我无法在Python中找到一个库来完成这个任务，所以我使用的是CGAL & C++。我让它在大多数象形文字上运行得很好，但它在其他人身上却神秘地失败了。

最初，我对CGAL印象深刻。它看起来非常全面和复杂，似乎提供了我所需要的所有功能，但是它有一个致命的缺陷--我几乎无法相信--库中没有错误处理。没有错误代码，没有异常，只有断言--但只在调试版本中。在版本构建中，您会得到一个很好的分段错误。此外，这些断言没有揭示问题的性质。

程序只在某些符号上失败。字母e工作得很好，但是它在a上崩溃了。当我试图计算字形与水印的合并时，就会发生崩溃。“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;

任何帮助都将不胜感激。谢谢。

编辑：

我有一个名为几何学的模块，它封装了CGAL代码，并公开了一系列几何原语(点、曲线、LineSegment、CubicBezier、路径)和函数：

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设置为曲线的最后一点，以防它们稍有不同。我希望这能解决这个问题，但事实并非如此。我想不出任何其他可能会使这些形状失效的东西。

以下是“e”字形与水印(an )的成功合并。

这是'a‘字形的样子。合并在此字形上失败。

编辑2：

下面是从PostScript解析后构成'a‘字形的曲线。它似乎没有什么问题。就像我说的，渲染的时候看起来没问题。此错误可能发生在将此数据转换为CGAL类型时。线段被转换成带有两个控制点的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-单调的。

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