CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
5.02k stars 1.39k forks source link

fix the fatal bug of the convolution calculation part of the Minkowski sum #8573

Closed Garbage123King closed 1 week ago

Garbage123King commented 1 month ago

Summary of Changes

Modify the convolution calculation part of the Minkowski sum. In the 'elimination of antennas' phase, before I fix it, only the antennas of the first segment were eliminated, skipping the possible subsequent antennas. For more details, please refer to the explanation in the issue. I modified it so that if a new antenna is merged, the newly merged antenna is used as curr for the next iteration; otherwise, after_next is used as curr.

Release Management

efifogel commented 2 weeks ago

BW, consider the Minkowski sum of two 2 segments, that is, two degenerate polygons. I've noticed that now, while the full-convolution method works, the reduced convolution (which is the default) fails. The decomposition method also works on this case. I guess more rigorous tests are needed, but the manual does not say that such degenerate cases are expected to work though. As Garbase123King said, mathematically, they should all work...

sloriot commented 2 weeks ago

Successfully tested in CGAL 6.1-Ic-15

github-actions[bot] commented 2 weeks ago

This pull-request was previously marked with the label Tested, but has been modified with new commits. That label has been removed.