CGAL users discussion list

[Efi Fogel <>]

Michael George wrote:
> Hi,
>
> For my application I would like to be able to find points on the 
> boundary of the minkowski sum of the interior of some polygons, but it 
> looks like the new code for minkowski sums drops the lower-order 
> features.  I would also like to take sums of objects that are composed 
> of lines and circular arcs, although that's not as important to me 
> since I can at least sum polygons and circles.
>
> Can anyone advise me on whether CGAL does in fact support this, 
> whether there are plans for it in the future, and whether it might be 
> feasible for me to modify the existing code to support this?
Regarding the lower-order features, I assume that it is possible to 
exploit the existing code. It means that the input operands may have 
lower-order features, and that they must be represented somehow. One 
solution is as follows:
1. Identify the lower-order features, remove them, and obtain simple 
polygons.
2. Compute the Mink. sum of the simple polygons using the 
Minkowski_sum_2 package
3. Compute the Mink. sum of pairwise point sets that have lower-order 
features. This is a relatively easy task, and results with points sets 
the boundary of which may have lower-order features
4. Identify the lower-order features, remove them, and obtain simple 
polygons.
5. Compute the union of the results of 2. and 4 using the 
Boolean_set_operation_2 package
6. Compute the union of the results of 5 and lower-order features 
identified at 4.

Alternatively, instead of steps 4., 5., and 6., you might be able to use 
Nef_2.

Indeed, the code supports computations of Minkowski sum of (linear) 
polygons and of a (linear) polygon and a (whole) disc. At this point 
there are no plans to enhance the code to supports point sets the 
boundaries of which are different than the above.

In general, our aim was to stay within the (exact) rational arithmetic 
realm. The Minkowski sum of point sets the boundaries of which have 
circular arcs might be something that cannot be computed and represented 
using rational arithmetic. Let us know in case you decide to modify the 
code yourself and need further help.
> Thanks!
>
> Mike
--
  ____  _        ____             _
 /_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/