CGAL二维正则化布尔集运算lib线程安全吗？

Question

我目前使用的是标题中提到的库，参见

CGAL 2D-reg-bool-set-op-pol

该库提供了多边形和多边形集的类型，这些类型在内部被表示为所谓的安排。

我的问题是：这个库在多大程度上是线程安全的，也就是说，适合对其对象进行并行计算？

线程安全的保证可能有几个层次。

1) 如果我从一个库中取出一个对象，比如一个排列体。

Polygon_set_2 S;

我也许可以执行

Polygon_2 P;
S.join(P);

和

Polygon_2 Q;
S.join(Q);

在两个不同的并发执行单元中并行地执行线程，而不会受到伤害，并得到正确的结果，就像我按顺序做所有的事情一样。这将是线程安全度最高的并行性。

2）其实对我来说，一个小得多的程度就够了。在这种情况下，S和P将是一个类C的成员，所以两个类实例有不同的S和P实例。那么我想计算（比如说 S.join(P) 对C类的实例列表进行并行处理，比如说，通过调用C类的一个合适的成员函数std::async

为了完整起见，我在这里插入一点我的项目中的实际代码，它给这些简明的描述提供了更多的内容。

// the following typedefs are more or less standard from the
// CGAL library examples.


typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                   Point_2;
typedef Kernel::Circle_2                                  Circle_2;
typedef Kernel::Line_2                                    Line_2;
typedef CGAL::Gps_circle_segment_traits_2<Kernel>         Traits_2;

typedef CGAL::General_polygon_set_2<Traits_2>             Polygon_set_2;
typedef Traits_2::General_polygon_2                       Polygon_2;
typedef Traits_2::General_polygon_with_holes_2            Polygon_with_holes_2;
typedef Traits_2::Curve_2                                 Curve_2;
typedef Traits_2::X_monotone_curve_2                      X_monotone_curve_2;
typedef Traits_2::Point_2                                 Point_2t;
typedef Traits_2::CoordNT                                 coordnt;
typedef CGAL::Arrangement_2<Traits_2>                     Arrangement_2;
typedef Arrangement_2::Face_handle                        Face_handle;

// the following type is not copied from the CGAL library example code but
// introduced by me
typedef std::vector<Polygon_with_holes_2> pwh_vec_t;


// the following is an excerpt of my full GerberLayer class,
// that retains only data members which are used in the join()
// member function. These data is therefore local to the class instance.

class GerberLayer
{
public:

    GerberLayer();
    ~GerberLayer();

    void join();

    pwh_vec_t raw_poly_lis;
    pwh_vec_t joined_poly_lis;

    Polygon_set_2 Saux;

    annotate_vec_t annotate_lis;

    polar_vec_t polar_lis;


};

//
// it is not necessary to understand the working of the function
// I deleted all debug and timing output etc. It is just to "showcase" some typical
// operations from the CGAL reg set boolean ops for polygons library from
// Efi Fogel et.al.
//
void GerberLayer::join()
{

    Saux.clear();

    auto it_annbase = annotate_lis.begin();

    annotate_vec_t::iterator itann = annotate_lis.begin();

    bool first_block = true;

    int cnt = 0;

    while (itann != annotate_lis.end()) {

        gpolarity akt_polar = itann->polar;

        auto itnext = std::find_if(itann, annotate_lis.end(),
                [=](auto a) {return a.polar != akt_polar;});

        Polygon_set_2 Sblock;

        if (first_block) {
            if (akt_polar == Dark) {

                Saux.join(raw_poly_lis.begin() + (itann - it_annbase),
                            raw_poly_lis.begin() + (itnext - it_annbase));
            }
            first_block = false;
        } else {
            if (akt_polar == Dark) {

                Saux.join(raw_poly_lis.begin() + (itann - it_annbase),
                                raw_poly_lis.begin() + (itnext - it_annbase));

            } else {


                Polygon_set_2 Saux1;

                Saux1.join(raw_poly_lis.begin() + (itann - it_annbase),
                                raw_poly_lis.begin() + (itnext - it_annbase));


                Saux.complement();

                pwh_vec_t auxlis;

                Saux1.polygons_with_holes(std::back_inserter(auxlis));

                Saux.join(auxlis.begin(), auxlis.end());

                Saux.complement();

            }
        }

        itann = itnext;
    }

    ende:
    joined_poly_lis.clear();

    annotate_lis.clear();

    Saux.polygons_with_holes (std::back_inserter (joined_poly_lis));

}



int join_wrapper(GerberLayer* p_layer)
{
    p_layer->join();
    return 0;
}

// here the parallelism (of the "embarassing kind") occurs:
// for every GerberLayer a dedicated task is started, which calls
// the above GerberLayer::join() function

void Window::do_unify()
{
    std::vector<std::future<int>> fivec;

    for(int i = 0; i < gerber_layer_manager.num_layers(); ++i) {
        GerberLayer* p_layer = gerber_layer_manager.at(i);

        fivec.push_back(std::async(join_wrapper, p_layer));

    }

    int sz = wait_for_all(fivec); // written by me, not shown

}

有人可能会认为，2)一定是可能的，因为在游戏中只有 "不同 "的多边形和排列实例。但是。它是可以想象的，因为这个库可以使用任意精度的点(Point_2t 在我上面的代码中)，由于一些实现上的原因，所有的点都被插入到Point_2t类的静态列表中，所以相同的点在这个列表中只表示一次。因此，就不会有类似于 "Point_2t的独立实例 "的东西，因此也不会有 "Polygon_2 "或 "Polygon_set_2"，人们可以告别线程安全。

我试图通过谷歌来解决这个问题（我必须承认，不是通过分析库代码），希望得到一个权威的答案（希望是正面的，因为这种原始的并行性会大大加快我的代码）。

补充：1)我已经实现了这个功能，并做了测试，没有什么特殊情况发生，视觉上的结果也是可信的，当然这不能证明什么。

2)同一作者的CGAL 2D-Arrangement-package也有同样的问题。

先谢谢你了

P.S.: 我使用的是Ubuntu 16.04 (Xenial)提供的软件包中的CGAL 4.7。在Ubuntu 18.04上的一个新版本给我带来了错误，所以我决定继续使用4.7。如果一个比4.7更新的版本是线程安全的，但不是4.7，我当然会尝试使用那个更新的版本。

顺便说一下，我无法找到Ubuntu 16.04提供的libcgal***.so库是否像文档中描述的那样是线程安全的。特别是当我在启动板上查看Xenial cgal包的构建日志时，我没有发现文档中 "线程安全 "部分提到的宏变量CGAL_HAS_THREADS。

Answer 1

事实上有几个级别的线程安全.2D Regularized Boolean操作包依赖于2D Arrangement包，而这两个包都依赖于一个内核。对于大多数操作都需要EPEC内核.这两个包都是线程安全的,除了有理弧特征(Arr_rational_function_traits_2)。然而，EPEC内核在线程间共享数字型对象时还不是线程安全的。所以，如果你，在不同的线程中，分别从不同的曲线输入集构造不同的排列，你是安全的。