Polygon Partition

CGAL provides the polygon partion algorithm for polygons and polygons with holes. This can be used to break the polygon down into convex pieces.

This is provided through the PolygonPartition2 class of which a static instance can be used as follows.

//Create a polygon.
var polygon = PolygonFactory<EIK>.KochStar(30, 3);

//Get the instance object.
var instance = PolygonPartition2<EIK>.Instance;

//If you know the input is good then checking 
//can be disabled which can increase perform.
//instance.CheckInput = false;

var results = new List<Polygon2<EIK>>();
instance.Partition(polygon, results);

foreach(var poly in results)
{
    poly.Print();
}

The method to use can be provided.

var method = POLYGON_PARTITION.OPTIMAL_CONVEX;

var results = new List<Polygon2<EIK>>();
instance.Partition(method, polygon, results);

The algorithm also provides a way to check if the polygon is y-monotonic. This is important for line sweep algorithms.

//Create a polygon.
var polygon = PolygonFactory<EIK>.KochStar(30, 3);

//Get the instance object.
var instance = PolygonPartition2<EIK>.Instance;

if(instance.Is_Y_Monotone(polygon))
{
   //do something.
}

Below is a image of the koch star being partitioned.