线程安全三角剖分库

Question

我正在编写一个C++软件，它需要快速的Minkowski和计算。一种基于双足的实现。

我评估了一些几何库，例如

• CGAL
• 丽达
• 助推：：几何 (没有Minkowski求和实现，但有一个教程解释如何实现它)

但我最后使用了另一个第三方库，它与以前的库相比非常快，它使用拳拳库进行三角剖分。

我的代码或多或少以以下方式工作：

• 我读我的多边形
• 我计算我需要的Minkowski和
• N次
  • 我决定在下面的计算中使用哪一个多边形
  • 我做了一些基于Minkowski和的事情
  • 我给出了结果的值

​

• 我以最优的结果作为最终结果。

由于循环中的计算是独立的，所以我将循环并行化，一切都很好。

然后，我决定在每一轮并行计算中移动Minkowski和计算：

• 我读我的多边形
• 对于number_of_threads(=n)乘以
  • 我决定在下面的计算中使用哪一个多边形
  • 我计算了这一轮我需要的Minkowski和
  • 我做了一些基于Minkowski和的事情
  • 我给出了结果的值

​

• 我以最优的结果作为最终结果。

但是第三方图书馆不再起作用了。

我收到number_of_threads - 1错误消息说

断言失败。

导致断言失败的文件在运行到运行和线程之间都会发生变化，但它们都是c-文件，与第一个头文件的名称相同(虽然我有第三方库的源代码，但是只有一个.lib和第一个库的头)。

如前所述，我试图计算并行代码之外所需的所有Minkowski和，并在其中使用结果。这没问题。所以我几乎可以肯定这些问题来自于第一次。

我有两个问题：

• 您知道拳拳库是否线程安全吗？
• 如果没有，你能建议我一个线程安全的(C或者更好的) C++三角剖分库来代替F拳头(可能有类似的性能)吗？

编辑：

实际上，我不知道“线程安全”是否正是我想要的:我只需要一个可以同时计算多个独立三角剖分的跟踪库。

我认为如果库没有全局变量，如果它有一个没有static变量的类

class triangulation
{
    // no static variables

    void execute_triangulation();
}

可能就够了。因此，我可以使用该类的不同实例并并行运行它们的方法。

Answer 1

您可能可以使用CGAL的二维三角剖分软件包替换FIST，然后将其用作执行Minskowski和的第三方库的输入。CGAL三角剖分速度快，可靠性高。您可以使用约束Delaunay三角剖分来对多边形和复杂形状进行三角剖分。

顺便问一下，你用的是明考斯基图书馆吗？

Answer 2

一个可以立即测试的解决方案是在调用Minkowski计算的代码周围放置一个互斥。如果这听起来很有趣，而且你不知道该怎么做，那么添加一条评论，详细说明你正在使用的平台，我或者其他人，会概述如何做到这一点。

至少，这将向您展示您是否正确地识别了问题。如果计算只占您总带宽的一小部分，那么它可能是一个很好的解决方案--否则只是一步之遥。

Answer 3

这在很大程度上取决于你的意思：

由于我的代码是可并行的，所以引入了多线程。

你需要更具体一些才能得到帮助。“你引入了多线程”是什么意思？例如，您提到的库中没有一个库具有内置的Minkowski和(或其他任何东西)的并行计算--您需要自己将其并行化。

关于Minkowski和，可以使用map-reduce方法:将输入数据集分割成较小的部分，并行计算Minkowski和(map)，并将来自独立工作人员的中间结果合并(还原)。这方面的要求是一个基本的线程安全保证(例如，CGAL给您提供的)，对计算参数的只读访问。