CGAL users discussion list

[Mariette Yvinec <>]

Mariette Yvinec wrote:

> Johan Van den Neste wrote:
>
> > It doesn't look like it is in the library, but how would I go about
> > producing a similar result? (doesn't need to be optimal)
> >
> > thanks,
> look at Partition_2 package

In fact  Partition_2 will not solve your problem because it does not handle
polygons with holes.
You can  solve your problem using a Constrained_Delaunay_triangulation_2.
Input the boundaries of your input polygons in a 
Constrained_Delaunay_triangulation_2.
Then visit all the triangulation edges and mark the edges that are not 
constrained edges
and can be discarded without giving reflex vertices in region of interest.
The  remaining edges  give you a convex decomposition with at most twice 
the optimal
number of parts.