Stream Triangulation Library

Question

I am writing C ++ software that requires fast calculations of the Minkowski sum . A dual-based implementation is sufficient.

I appreciated some geometric libraries such as

• Cgal
• ICE
• boost :: geometry (does not have an implementation of the Minkowski sum, but there is a guide explaining how to implement it)

but in the end I used another third-party library that works very fast compared to the previous ones and uses the FIST library for triangulation.

My code works more or less as follows:

• I read my polygons
• I calculate the Minkowski sums I need
• For n times
  • I decide which polygons to use in the following calculations.
  • I do some things based on Minkowski sums
  • I evaluate the result
• I take the result with the best value as the end result

Since the calculations inside the loop are independent from loop to loop, I parallelized the loop and everything worked fine.

Then I decided to move the calculation of the Minkowski sum in each parallel round:

• I read my polygons
• For number_of_threads (= n) times
  • I decide which polygons to use in the following calculations.
  • I calculate the Minkowski sums I need in this round
  • I do some things based on Minkowski sums
  • I evaluate the result
• I take the result with the best value as the end result

but the third-party library no longer worked.

I get number_of_threads - 1 error message saying

Approval failed.

The files that cause the assertion error vary from run to run and from thread to thread, but they are all files with the same name as the FIST headers (although I have the source code of a third-party library, I only have a. Lib and FIST library headers)

As indicated earlier, I tried to calculate all the Minkowski sums I needed outside the parallelized code and use the results obtained in it. That was good. So I'm pretty sure the problems come from FIST.

I have two questions:

• Do you know if the FIST library is thread - oriented ?

• If not, could you please offer me a thread-safe (C or better) C ++ triangulation library to replace FIST (possibly with comparable characteristics)?

edit:

Actually, I don’t know if the “thread safe” is exactly what I want: I only need a trimming library that can calculate many independent triangulations at the same time.

I think that if there were no global variables in the library and if it had a class without static variables

 class triangulation { // no static variables void execute_triangulation(); } 

that may be enough. Therefore, I could use different instances of this class and run their method in parallel.

Answer 1

Perhaps you can use the CGAL 2D triangulation package to replace FIST, and then use it as an input to this third-party library that makes Minskovsky. CGAL triangulations are very fast and reliable. You can triangulate polygons and complex shapes using Delaney's limited triangulation.

By the way, which Minkowski library are you using?

Answer 2

One possible and immediately verifiable solution is to place the mutex around the code that invokes Minkowski's calculations. If this sounds interesting and you don’t know how to do it, add a comment detailing the platform you are using, and I or someone else will tell you how to do it.

At the very least, this will show you whether you have identified the problem correctly. If calculations make up a small part of your total bandwidth, then this may turn out to be a good solution - otherwise it’s just a step on the road.

Answer 3

It depends a lot on what you mean by this:

Since my code is parallelizable, I introduced multithreading

You need to be more specific in order to get help. What does it mean you entered multithreading? For example, none of the libraries that you mentioned have a parallel calculation of the Minkowski sums (or anything else) built into it, you will need to parallelize it yourself.

As for the Minkowski sums, you can use the approach to reduce the map: divide the input data set into smaller parts, calculate the Minkowski sum for each in a parallel (map) and combine the intermediate results as they come from independent workers (reduction). The requirements for this are a basic guarantee of thread safety (which, for example, CGAL gives you) read-only access to calculation parameters.