c++ - 具有多边形交集和不精确构造内核的 CGAL Precondition_exception

Question

我在使用 CGAL 时遇到了一些奇怪的错误，我无法在小型测试程序中重现该错误。这是按给定的方式运行的测试代码，但是当我在较大的程序(ROS 节点)中使用完全相同的代码时，它会报错:

#include <vector>
#include <boost/shared_ptr.hpp>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Boolean_set_operations_2.h>

#include "print.h"

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT                          Ft;
typedef Kernel::Point_2                     Point;
typedef Kernel::Segment_2                   Segment;
typedef Kernel::Direction_2                 Direction;
typedef Kernel::Line_2                      Line;
typedef Kernel::Vector_2                    Vector;
typedef CGAL::Polygon_2<Kernel>             Polygon;
typedef CGAL::Polygon_with_holes_2<Kernel>  PolygonWithHoles;

main() {
    Polygon poly;

    float scale = 4.0/100;
    float max_y = 500*scale;
    poly.push_back(Point(76*scale, max_y-496*scale));
    poly.push_back(Point(660*scale, max_y-496*scale));
    poly.push_back(Point(660*scale, max_y-48*scale));
    poly.push_back(Point(71*scale, max_y-54*scale));

    // Holes must be clock wise!!
    Polygon holes[10];
    holes[0].push_back(Point(131*scale, max_y-86*scale));
    holes[0].push_back(Point(179*scale, max_y-85*scale));
    holes[0].push_back(Point(180*scale, max_y-238*scale));
    holes[0].push_back(Point(133*scale, max_y-239*scale));

    holes[1].push_back(Point(237*scale, max_y-84*scale));
    holes[1].push_back(Point(286*scale, max_y-84*scale));
    holes[1].push_back(Point(288*scale, max_y-237*scale));
    holes[1].push_back(Point(240*scale, max_y-238*scale));

    // Why does this hole make intersection() error?
    holes[2].push_back(Point(345*scale, max_y-84*scale));
    holes[2].push_back(Point(393*scale, max_y-83*scale));
    holes[2].push_back(Point(396*scale, max_y-236*scale));
    holes[2].push_back(Point(348*scale, max_y-236*scale));

    PolygonWithHoles polyHoles(poly);
    polyHoles.outer_boundary() = poly;
    for (int i=0; i<3; ++i)
        polyHoles.add_hole(holes[i]);

    std::cout << "\nPolygon:" << std::endl;
    print_polygon_with_holes(polyHoles);

    Polygon selection;
    float minx = -5.7669;
    float miny = -2.13124;
    float maxx = 0.396996;
    float maxy = 4.88933;

    selection.push_back(Point(minx, miny));
    selection.push_back(Point(maxx, miny));
    selection.push_back(Point(maxx, maxy));
    selection.push_back(Point(minx, maxy));

    std::cout << "\nSelection:" << std::endl;
    print_polygon(selection);

    std::vector<PolygonWithHoles> result;
    CGAL::intersection(polyHoles, selection, std::back_inserter(result));

    std::cout << "Intersection:" << std::endl;
    if (!result.empty())
        print_polygon_with_holes(result.front());
}

错误:

terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: comp_f(object, parentP->object) != SMALLER
File: /usr/include/CGAL/Multiset.h
Line: 2128

我找到了 2 种方法来解决这个问题:

1. 稍微移动一点:将 83 替换为 84。
2. 使用 Exact_predicates_exact_constructions_kernel

我的问题是:是什么导致问题只存在于较大的程序中？

我想继续使用 unexact_constructions，我不明白为什么在这种情况下我必须使用 exact_constructions(点彼此不靠近或任何东西)，但因为我不知道intersection() 算法的作用我可能错了。

Answer 1

intersect 函数构造新点 - 新的交点。如果你没有使用精确的结构，那么这些新点就不会被保证是正确的。如果您随后使用这些不精确的点进行进一步计算，您将遇到问题。除非您对运行时间有重大限制，否则我相信您最好使用精确的构造。

示例:考虑单位圆 x^2+y^2=1 和直线 y=x 并设 p 为构造的交点。然后 circle.has_on_boundary (p) 将返回 TRUE 仅当您使用确切的构造时。