2D Polygon Partitioning

18.1 | Introduction | ||||

18.2 | Monotone Partitioning | ||||

18.3 | Convex Partitioning |

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 18.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(n ^{4})* time and $$

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