CGAL users discussion list

[Fernando Cacciola <>]

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).

Best

Fernando Cacciola

www.geometryfactory.com