Утверждение, инициированное в CGAL при вычислении многоугольника

Question

Я пишу приложение на Python, которое применяет водяной знак к файлу шрифта. Глифы представляют собой невыпуклые многоугольники с дырками и состоят из сплайнов сплайнов, определенных в PostScript. Водяной знак должен сливаться с глифами, а не перекрываться. Мне не удалось найти библиотеку, чтобы сделать это на Python, поэтому я использую CGAL & C++. Я хорошо работаю над большинством глифов, но таинственно терпит неудачу на других.

Первоначально, я был очень впечатлен CGAL. Он выглядел очень всеобъемлющим и сложным и, казалось, предоставлял все необходимые мне функции, но он страдает одним фатальным недостатком - и я почти не могу поверить в это - библиотека не содержит ошибок обработки. Нет кодов ошибок, исключений, просто утверждений, но только в сборке отладки. В сборке вы получите вместо этого хорошую ошибку сегментации. Более того, утверждения показывают ничего о характере проблемы.

Программа не работает только на определенных глифах. Буква «e» отлично работает, но она падает на «a». Сбой происходит, когда я пытаюсь вычислить объединение глифа с водяным знаком. Нет ничего явно неправильного с символом 'a'. Мое приложение правильно анализирует PostScript и отлично отображает его в QGraphicsView.

Эта программа должна запускаться на сервере, а ее вывод отправляется непосредственно клиенту, поэтому он должен быть надежным. Я не могу оправиться от неудачи утверждения или segfault, так что я могу сделать?

Даже если я получу его работу надежно, как я могу доверять, что он никогда не провалится? Если бы была какая-то обработка ошибок, я мог бы просто пропустить несколько глифов, с которыми она терпит неудачу, оставив их без водяных знаков - не идеальными, но приемлемыми. Я просто не понимаю, что думают авторы этой библиотеки; они пошли на такие огромные усилия, чтобы получить самую полную библиотеку геометрии, доступную только для того, чтобы убедиться, что она совершенно непригодна для цели.

В настоящее время это похоже на то, что мне придется изменить код сам, чтобы обработать ошибку разумным способом, но это просто кажется таким смешным.

Прошу прощения, если я оторвусь от нетерпения, но я прошел мимо моего срока, и мой клиент не заботится о них или не понимает этих оправданий.

провал утверждение происходит на линии 2141 из multiset.h:

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

Это происходит, когда я звоню присоединиться() на BezierPolygonSet. Мои типы таковы:

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; 

Любая помощь будет очень признательна. Благодарю.

EDIT:

У меня есть модуль под названием Геометрия, которая оборачивает код CGAL и выставляет кучу геометрических примитивов (точка, кривая, 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); 
} 

ошибка возникает, когда я звоню присоединиться().Полигоны созданы из путей, как так:

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

Обратите внимание, что я тщательно, чтобы гарантировать, что границы полигонов нет пробелов, установив первую точку кривой п + 1 к последней точке кривой п в случае они были немного разными. Я надеялся, что это решит проблему, но это не так. Я не могу придумать никаких других вещей, которые могли бы сделать фигуры недействительными.

Вот успешное слияние глифа «e» с водяным знаком (X).

Вот что представляет собой символ 'a'. Слияние не выполняется на этом символе.

EDIT 2:

Вот кривые, которые составляют 'а' глиф после разбора его из PostScript. В этом нет ничего плохого. Как я уже сказал, при визуализации все выглядит нормально. Вероятно, ошибка возникает при переводе этих данных в типы 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)] 

EDIT 3:

Вот 'а' кривые глифа после перевода в кривые CGAL. Обратите внимание, что они точно соответствуют кривым перед переводом, подразумевая, что ни один из них не должен быть разбит на 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 

Этот многоугольник вызывает сбой утверждение при добавлении к BezierPolygonSet. Есть идеи?

Answer 1

1. Вы можете настроить обработку ошибок; см. manual.
2. Пожалуйста, приложите полную автономную программу. Ничто не выглядит неправильным для меня с заявлениями, которые вы указали.

Вы можете аппроксимировать кривые Безье полилиниями и обработать все, используя полилинии. Если проблема связана с обработкой кривых Безье, то это решит ее. Если это приемлемо, оно также будет более эффективным.

Мы зафиксировали ошибку в компоненте CGAL, который обрабатывает кривые Безье, а именно Arr_Bezier_curve_traits_2.h.