CGAL users discussion list

[Alfredo Olivera <>]

Thanks Fernando for your reply.
> Hello Alfredo,
>
> > Hello.
> >
> > Given a 2D polygon, I need to determine a new polygon which is very 
> > similar to it but has much less vertices.
> >
> > This is part of a pre-processing step of an optimisation algorithm in 
> > which I receive a polygon with ~2,000 vertices (which make any 
> > optimisation unusable) and I want to simplify it to ~100 vertices.
> >
> > I do not have a quality measure to determine which approximation is 
> > better, so I am open in this sense. The data I have is such that an 
> > approximation is feasible (I have done it by hand, achieving good 
> > results).
> >
> > There are two flavours of the problem:
> >
> >  1) The new polygon must be totally contained in the original polygon
> >  2) The new polygon must totally contain the original polygon
> >
> > Do we have any CGAL package that may help me on this?
> We will.. there is work in progress for *precisely* this (specifically 
> the variant where the simplified polygon contains a subset of the 
> vertices of the original).
Actually it does not matter for me if the polygons share vertices or 
not. I am prepared to accept a polygon which has no common vertices with 
the original, provided it gives me a good approximation.

Alfredo