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. The computed partition polygons, whose vertices are also oriented counterclockwise, are written to the sequence starting at position result and the past-the-end iterator for the resulting sequence of polygons is returned. The traits classes for the functions specify the types of the input points and output polygons as well as a few other types and function objects that are required by the various algorithms.
For checking the validity of the partitions produced by y_monotone_partition_2, we provide a function is_y_monotone_2, which determines if a sequence of points in 2D defines a y-monotone polygon or not. For examples of the use of these functions, see the corresponding reference pages.
Figure 22.1: Examples of an optimal convex partition (left) and an approximately optimal convex partition (right).
An optimal convex partition can be produced using the function optimal_convex_partition_2. This function provides an implementation of Greene's dynamic programming algorithm for optimal partitioning [Gre83]. This algorithm requires O(n4) time and O(n3) space in the worst case.
The function approx_convex_partition_2 implements the simple approximation algorithm of Hertel and Mehlhorn [HM83] that produces a convex partitioning of a polygon from a triangulation by throwing out unnecessary triangulation edges. The triangulation used in this function is one produced by the 2-dimensional constrained triangulation package of Cgal. For a given triangulation, this convex partitioning algorithm requires O(n) time and space to construct a decomposition into no more than four times the optimal number of convex pieces.
The sweep-line approximation algorithm of Greene [Gre83], which, given a monotone partition of a polygon, produces a convex partition in O(n log n) time and O(n) space, is implemented by the function greene_approx_convex_partition_2 . The function y_monotone_partition_2 described in Section 22.2 is used to produce the monotone partition. This algorithm provides the same worst-case approximation guarantee as the algorithm of Hertel and Mehlhorn implemented with approx_convex_partition_2 but can sometimes produce better results (i.e., convex partitions with fewer pieces).
Examples of the uses of all of these functions are provided with the corresponding reference pages.