
namespace CGAL {
/*!

\mainpage User Manual 
\anchor Chapter_2D_Polygon_Partitioning
\anchor chappolygonpartition
\cgalAutoToc
\author Susan Hert

\section secpartition_2_intro Introduction 

A <I>partition</I> of a polygon \f$ P\f$ is a set of 
polygons such that the 
interiors of the polygons do not intersect and the union of the polygons 
is equal to the interior of the original polygon \f$ P\f$. 
This chapter describes functions for partitioning
planar polygons into two types of subpolygons - \f$ y\f$-monotone polygons and
convex polygons. The partitions are produced without introducing new
(Steiner) vertices.

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.

\section secpartition_2_monotone Monotone Partitioning 

A <I>\f$ y\f$-monotone polygon</I>
is a polygon whose vertices \f$ v_1, \ldots, v_n\f$ can be divided into two chains 
\f$ v_1, \ldots, v_k\f$ and \f$ v_k, \ldots, v_n, v_1\f$, such that any horizontal line 
intersects either chain at most once. For producing a \f$ y\f$-monotone partition 
of a given polygon, the sweep-line algorithm 
presented in \cgalCite{bkos-cgaa-97} is implemented by the function
`y_monotone_partition_2()`. This algorithm runs in \f$ O(n \log n)\f$ time and requires \f$ O(n)\f$ space.
This algorithm does not guarantee a bound on the number of polygons 
produced with respect to the optimal number.

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 \f$ y\f$-monotone
polygon or not. For examples of the use of these functions, see the
corresponding reference pages.


\section secpartition_2_convex Convex Partitioning 

Three functions are provided for producing convex partitions of polygons.
One produces a partition that is optimal in the number of pieces. 
The other two functions produce approximately optimal convex partitions.
Both these functions produce convex decompositions by first decomposing the 
polygon into simpler polygons; the first uses a triangulation and the second a
monotone partition. These two functions both guarantee that they will produce 
no more than four times the optimal number of convex pieces but they differ in 
their runtime complexities. Though the triangulation-based approximation
algorithm often results in fewer convex pieces, this is not always the case.


\cgalFigureBegin{P2_approxvsopti,approximate_optimal_vs_optimal.png}
Examples of an approximate optimal convex partition (left) and an optimal convex partition (right).
\cgalFigureEnd

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 \cgalCite{g-dpcp-83}. 
This algorithm requires \f$ O(n^4)\f$ time and \f$ O(n^3)\f$ space in the worst case. 

The function `approx_convex_partition_2()` implements the simple approximation 
algorithm of Hertel and Mehlhorn \cgalCite{hm-ftsp-83} 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 \f$ O(n)\f$ 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 \cgalCite{g-dpcp-83}, which, 
given a monotone partition of a polygon, produces a convex partition in 
\f$ O(n \log n)\f$ time and \f$ O(n)\f$ space, is implemented
by the function `greene_approx_convex_partition_2()`. The function
`y_monotone_partition_2()` described in
Section \ref secpartition_2_monotone 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.

*/ 
} /* namespace CGAL */

