CGAL users discussion list

[Michael George <>]

 wrote:
> Quoting Michael George 
> <>:
>
> > Greetings,
> >
> > I've been struggling for some time now to extend the minkowski sum code
> > in CGAL to produce non-regularized output (i.e. to retain the low
> > dimensional features).  I've explored a variety of designs to perform
> > the union of cycles, but it seems to me like the arrangement package is
> > just slightly too inflexible to accomodate each design.  I have two
> > questions:
>
> I guess it is a matter of opinion, but I would say that the 
> arrangement package is a good choice to accomplish your task. Besides, 
> what do you mean by 'each' above?
>
> > 1. Has anyone managed to do this?  If so, how?
>
> Do what exactly? The Minkowski sum package supports two different 
> methods to compute the exact Minkowski sum, one uses decomposition and 
> union, and the other is based on convolution. The latter may already 
> handle the low dimensional features. The former does not, because it 
> uses the union operation, which does not, so the problem reduces to 
> computing the non-regularized union. What type of boundary curves are 
> we talking about?
Be 'each' I mean each design I've come up with to perform the union (I'm 
admittedly not that clever which is why I'm asking for advice).  The 
problem I keep having is that in order to support finding the 
low-dimensional features (points in particular) of the boundary, one 
needs to traverse the original cycles in order and mark the half-edges 
that are on the inside of the path.  I can't find any correct way to 
keep these information up to date as the arrangement package constructs 
the arrangement.

The current minkowski sum (by convolution) code works by storing some 
data in the x monotone curve objects, and updating this on intersect and 
split.  But in order to keep this ordering information up to date, it 
would have to do destructive updates, which it can't because the caller 
of intersect must throw out part of the output.

I've considered using the arrangements with history, but they provide no 
way to perform an _ordered_ traversal of the original curves.  This 
ordering is key.

I've considered using an overlay-based solution to do incremental 
merging, but this doesn't solve the problem because even an individual 
convolution cycle can double back on itself, so putting the individual 
cycles into the arrangement to compute the overlay brings up the same 
problems above.

The best I can think of is to delve into the arrangement code and 
provide more flexibility for updating data structures as curves are 
added to the arrangement, but if I'm digging that far down in the stack 
I'm not sure there's still a lot of benefit to not setting off and 
writing special purpose code.  I lose the advantage of using a 
well-tested, widely used library, but I'll gain simplicity and 
flexibility in the design.

I'd ultimately like to use this for curves that are a mix of line 
segments and arcs, but I'd be happy for starters to get it working with 
polygons.  Obviously if I want to extend it to arcs, I would have to 
significantly modify the code that generates the convolution cycles as 
well. 

Thanks for your help.

--Mike