Iterative Minkowski Difference optimization #289
Replies: 1 comment 5 replies
-
|
Copied from #288:
It is difficult to suggest the optimisation of the Obviously the optimisation is only possible by moving significant computations out of the nested loop that gives this Is that an answer you are looking for? |
Beta Was this translation helpful? Give feedback.
-
|
I will shorten my question, maybe that would be much clearer. Is there any way to make the for loop parallel in my specific case? I am trying to parallelize following loop, but it crashes upon running the application: std::vector<int> indexes(placed_paths.size()); // vector with placed_paths size ints.
std::iota(std::begin(indexes), std::end(indexes), 0); // Fill with 0, 1, ..., placed_paths size
std::for_each(std::execution::par, indexes.begin(), indexes.end(), [&](size_t i)
{
// int i = indexes[i];
//std::cout << indexes[i] << '\n';
for (int j = 0; j < placed_paths[indexes[i]].size(); j++) //
{
Clipper2Lib::Paths64 mink_diff = Clipper2Lib::MinkowskiDiff(pattern[0], placed_paths[indexes[i]][j], true); // take only boundary of the element
size_t start = -1;
size_t end = -1;
if (placed_pattern_or_path[indexes[i]])
{
start = j != 0 ? 1 : 0;
end = j != 0 ? mink_diff.size() : 1;
}
else
{
start = j == 0 ? 1 : 0;
end = j == 0 ? mink_diff.size() : 1;
}
// print(start, end);
for (int w = start; w < end; w++)
result.emplace_back(mink_diff[w]);
} }); |
Beta Was this translation helpful? Give feedback.
-
|
In generic case when no assumption could be made on input data set, there are two possible approaches and a combination of them, three in total:
Edit: these both are not an optimisation, but speedup by utilizing CPU resources. Otherwise, it could come up that some optimisations could be done as you add a path to the path list after each iteration, but this requires data analysis and may not be an universal solution. Edit2: |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for the reply. Really appreciate it. Could explain why boost threading would be better than C++ parallel for each? I have a minimal experience in C++ threading therefore a code snippet would be much appreciated. |
Beta Was this translation helpful? Give feedback.
-
it's was just a suggestion, not a recipe. C++ parallel could be used as well and I noted this in my Edit2 to the previous answer
Then you put an extra question "why my code segfaults?". Obviously the problem is not as straightforward as |
Beta Was this translation helpful? Give feedback.
-
|
Here you are: On linux the code has to be compiled with |
Beta Was this translation helpful? Give feedback.
-
Hi,
I am developing a nesting method using Clipper2 and Minkowski difference.
But the method is quite slow after 120 iterations the total execution time goes above 300 ms.
This process is iterative:
In the screenshots I am using the same square element, but in reality every nth element will be different.
That is the reason why I need to recompute minkowski difference each time.
First I thought that boolean union takes the most time, but the most time is used for Minkowski difference in the following code.
Question
Could you recommend what would be the best strategy to optimize the code because each part of the "Compute minkowski sum for two polygons with holes" takes more than 3-4 ms? Maybe a concept could be different for this problem? Any ideas would be much appreciated. Also why minkowski of clipper is using boolean union once you check this function in the source file?
What I am doing?
Iteration:1
Iteration:2
Iteration:3
Iteration:4
Iteration:120
Iteration time:
Beta Was this translation helpful? Give feedback.
All reactions