CGAL partitioning of polygon-with-holes

Question

I'm looking at the Partition_2 section of the manual and examples to see if CGAL can handle convex partitioning of a polygon with holes. All of the examples appear to use Polygons without any holes. Does anyone know if this is supported by any of the CGAL partitioning algorithms?

https://github.com/CGAL/cgal/blob/master/Partition_2/include/CGAL/partition_2.h

https://doc.cgal.org/latest/Partition_2/index.html

Thanks, Josh.

Answer 1

From the documentation:

All the partitioning functions present the same interface to the user. That is, the user provides a pair of input iterators, first and beyond, an output iterator result, and a traits class traits. The points in the range [first, beyond) are assumed to define a simple polygon whose vertices are in counterclockwise order.

Simple means no holes and no self intersection.

Handling polygons with holes is not hard to achieve since CGAL also provides boolean operations on polygons. Just create the partition and subtract the holes. This may not be an ideal solution if your use case is performance critical (directly partitioning a polygon with holes can be faster).

Answer 2

Right, the "2D Polygon Partitioning" package supports only polygons without holes (as far as I know). You can always triangulate a polygon with holes using the edges (on the outer and inner CCBs) as constraints. Another option is to use vertical decomposition. It is directly provided by the "2D Minkowski Sums" package; see Polygon_vertical_decomposition_2. It is based on the decompose(arr, oi) free function that accepts as input a 2D arrangement; see CGAL::decompose(). The output is a collection of pseudo trapezoids (a pseudo trapezoid can be a triangle in degenerate cases), so it's a bit "better" than pure triangles and extremely efficient, especially if you have the underlying arrangement at hand.