CGAL users discussion list

[Efi Fogel <>]

On Wed, Apr 6, 2016 at 5:51 PM, Samuel Hornus <> wrote:

On Apr6, 2016, at 16:38 , Efi Fogel <> wrote:

> There comes a new question however : What is the faster way to compute the Minkowski sum of a circular n-gon with a Polygon_set_2<> ? Should I extract the constituent Polygon_with_hole_2<>’s , compute the Minkowski sum for each and then recombine all the results in a union ?
>
> This sounds like a good plan.
>
> Notice that Minkowski sum of polygons with holes was introduced in CGAL in 4.7. This released featured two implementations, namely, a superior method in most cases based on convolution, and a decomposition into convex pieces that enables Minkowski sum of polygon with holes based on decomposition. In addition, another optimization for the decomposition based method is expected  to become available in version 4.9.

OK. Thank you Efi.
If it is plausible that computing the Minkowski sum directly on the Polygon_set_2 be even faster, then let me mark that a feature wish for a later release!

It's possible, especially since one of the summands is convex.

If and when you get to the point that you need to speed up your computation and you have sufficient test cases, drop a note, and we might be able to devise something.

 

Best regards,

Samuel

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss