CGAL 2D Regularized Boolean Set-Operations lib线程安全吗？

Question

我目前正在使用标题中提到的库，请参阅

该库提供多边形和多边形集的类型，它们在内部表示为所谓的排列。

我的问题是：这个库线程安全到什么程度，也就是说，适合在其 objects 上进行并行计算？

保证线程安全的级别可能有几个：

1) 如果我从图书馆拿一个 object 像编曲

Polygon_set_2 S;

我也许可以执行

Polygon_2 P;
S.join(P);

和

Polygon_2 Q;
S.join(Q);

在两个不同的并发执行中 units/threads 并行而没有伤害并得到正确的结果，就好像我按顺序完成了所有事情一样。那将是最高程度的线程 safety/possible 并行度。

2) 事实上，对我来说，低得多的学位就足够了。在那种情况下，S 和 P 将是 class C 的成员，因此两个 class 实例具有不同的 S 和 P 实例。然后我想为 class C 的实例列表并行计算（比如说）S.join(P)，比如说，通过使用 std::async[=18= 调用 C 的合适成员函数]

为了完整起见，我在此处插入了一些来自我的项目的实际代码，这些代码为这些简洁的描述提供了更多内容。

// 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) 一定是微不足道的，因为只有 "different" 个多边形和排列的实例在起作用。但是：可以想象，由于库使用任意精度点（我上面的代码中的 Point_2t），出于某些实现原因或其他原因，所有点都插入到 class 的静态列表中Point_2t，因此相同的点在此列表中只出现一次。所以不会有像 "independent instances of 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 更新的版本是 thread-safe，而不是 4.7，我当然会尝试使用那个更新的版本。

顺便说一句，我无法确定 Ubuntu 16.04 提供的 libcgal***.so 库是否如文档中所述是线程安全的。特别是当我查看启动板上 Xenial cgal 包的 build-logs 时，我没有发现文档 "thread-safety" 部分提到的 Macro-Variable CGAL_HAS_THREADS 的参考。

Answer 1

确实有几个级别的线程安全。 2D Regularized Boolean 运算包依赖于 2D Arrangement 包，并且这两个包都依赖于一个内核。大多数操作都需要 EPEC 内核。这两个包都是线程安全的，除了 rational-arc traits (Arr_rational_function_traits_2)。但是，EPEC 内核在线程间共享数字类型对象时还不是线程安全的。因此，例如，如果您分别从不同的输入曲线集在不同的线程中构造不同的排列，那么您是安全的。

CGAL 2D Regularized Boolean Set-Operations lib线程安全吗？

Is CGAL 2D Regularized Boolean Set-Operations lib thread safe?

concurrency

multithreading

cgal