CGAL users discussion list

[Efi Fogel <>]

On Wed, Apr 6, 2016 at 3:50 PM, Samuel Hornus <> wrote:

Thank you Efi, Monique,

In my particular case, I would always offset in the same direction (growing a generalized_polygon_set_2) and compute unions/intersection with straight polygons, so that I think that the intersection of two circular arcs would never become the center of a new circular arcs. But I should check that carefully.

Anyway, since this is all for a practical application (3d printing), I will probably go back to working with fully straight edges and use a Minkowski sum with a n-gon approximation of a disk, instead of offsetting. That should give satisfying precision, more speed and less headache.

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.

 

Best,

Samuel

On Mar31, 2016, at 14:58 , Efi Fogel <> wrote:

Yes, of course Monique is right. As a matter of fact, there is more to the story.

The approximate version, uses the Arr_circle_segment_traits_2 geometry traits model, which uses a certain number type called Sqrt_extension. This number type also represents algebraic numbers of degree 2, but has some constrains, which increases the efficiency of the supported operations. These constraints, naturally, limits its usages.

The exact version uses code that can handle conic arcs, so as far as number types are concerned (and as far as I can tell), it should suffice also for computing the offset of generalized polygons that comprise linear segments and circular arcs.

The bottom line doesn't change---the input must be a (linear) polygon.

However, perhaps with some limited effort, at least the exact version, can be extended to handle the desired generalized polygons.