CGAL 6.1.1 - 2D Polygon Partitioning

Loading...
Searching...
No Matches
Modules | Classes | Functions
Reference Manual

##

Susan Hert
This package provides functions for partitioning polygons in monotone or convex polygons. The algorithms can produce results with the minimal number of polygons, as well as approximations which have no more than four times the optimal number of convex pieces but they differ in their runtime complexities.
Introduced in: CGAL 2.3
BibTeX: cgal:h-pp2-26a
License: GPL

## Definitions

A partition of a polygon 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. Functions are available for partitioning planar polygons into two types of subpolygons (`y`-monotone polygons and convex polygons).

The function that produces a `y`-monotone partitioning is based on the algorithm presented in [1] which requires \(O(n \log n)\) time and \(O(n)\) space for a polygon with \( n \) vertices and guarantees nothing about the number of polygons produced with respect to the optimal number Three functions are provided for producing convex partitions. Two of these functions produce approximately optimal partitions and one results in an optimal partition, where optimal is defined in terms of the number of partition polygons. The two functions that implement approximation algorithms are guaranteed to produce no more than four times the optimal number of convex pieces. The optimal partitioning function provides an implementation of Greene's dynamic programming algorithm [2], which requires \(O(n^4)\) time and \(O(n^3)\) space to produce a convex partitioning. One of the approximation algorithms is also due to Greene [2] and requires \(O(n \log n)\) time and \(O(n)\) space to produce a convex partitioning given a `y`-monotone partitioning. The other approximation algorithm is a result of Hertel and Mehlhorn [3], which requires \(O(n)\) time and space to produce a convex partitioning from a triangulation of a polygon. Each of the partitioning functions uses a traits class to supply the primitive types and predicates used by the algorithms.

## Assertions

The precondition checks for the planar polygon partitioning functions are: counterclockwise ordering of the input vertices and simplicity of the polygon these vertices represent.

The postcondition checks are: simplicity, counterclockwise orientation, and convexity (or \( y\)-monotonicity) of the partition polygons and validity of the partition (i.e., the partition polygons are nonoverlapping and the union of these polygons is the same as the original polygon).

## Classified Reference Pages

## Concepts

- `ConvexPartitionIsValidTraits_2`
- `IsYMonotoneTraits_2`
- `OptimalConvexPartitionTraits_2`
- `PartitionTraits_2`
- `PartitionIsValidTraits_2`
- `YMonotonePartitionIsValidTraits_2`

## Function Object Concepts

- `PolygonIsValid`

## Classes

- `CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>`
- `CGAL::Partition_traits_2<R,P>`

## Function Object Classes

- `CGAL::Is_convex_2<Traits>`
- `CGAL::Is_vacuously_valid<Traits>`
- `CGAL::Is_y_monotone_2<Traits>`

## Functions

- `CGAL::approx_convex_partition_2()`
- `CGAL::convex_partition_is_valid_2()`
- `CGAL::greene_approx_convex_partition_2()`
- `CGAL::is_y_monotone_2()`
- `CGAL::optimal_convex_partition_2()`
- `CGAL::partition_is_valid_2()`
- `CGAL::y_monotone_partition_2()`
- `CGAL::y_monotone_partition_is_valid_2()`

## Modules
| Concepts
| Function Object Concepts
| Function Object Classes

## Classes
class | CGAL::Partition_is_valid_traits_2< Traits, PolygonIsValid >
| Class that derives a traits class for `partition_is_valid_2()` from a given traits class by defining the validity testing function object in terms of a supplied template parameter. More...
class | CGAL::Partition_traits_2< R, PointPropertyMap >
| Traits class that can be used with all the 2-dimensional polygon partitioning algorithms. More...

## Functions
template<class InputIterator , class Traits >
bool | CGAL::is_y_monotone_2 (InputIterator first, InputIterator beyond, const Traits &traits)
| determines if the sequence of points in the range [`first`, `beyond`) defines a \( y\)-monotone polygon or not.
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::approx_convex_partition_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
| computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into convex polygons.
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::greene_approx_convex_partition_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
| computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into convex polygons.
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::optimal_convex_partition_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
| computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into convex polygons.
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::y_monotone_partition_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
| computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into \( y\)-monotone polygons.
template<class InputIterator , class ForwardIterator , class Traits >
bool | CGAL::convex_partition_is_valid_2 (InputIterator point_first, InputIterator point_beyond, ForwardIterator poly_first, ForwardIterator poly_beyond, const Traits &traits=Default_traits)
| determines if the polygons in the range [`poly_first`, `poly_beyond`) define a valid convex partition of the polygon defined by the points in the range [`point_first`, `point_beyond`).
template<class InputIterator , class ForwardIterator , class Traits >
bool | CGAL::partition_is_valid_2 (InputIterator point_first, InputIterator point_beyond, ForwardIterator poly_first, ForwardIterator poly_beyond, const Traits &traits=Default_traits)
| returns `true` iff the polygons in the range [`poly_first`, `poly_beyond`) define a valid partition of the polygon defined by the points in the range [`point_first`, `point_beyond`) and `false` otherwise.
template<class InputIterator , class ForwardIterator , class Traits >
bool | CGAL::y_monotone_partition_is_valid_2 (InputIterator point_first, InputIterator point_beyond, ForwardIterator poly_first, ForwardIterator poly_beyond, const Traits &traits=Default_traits)
| determines if the polygons in the range [`poly_first`, `poly_beyond`) define a valid \( y\)-monotone partition of the simple, counterclockwise-oriented polygon represented by the points in the range [`point_first`, `point_beyond`).

## Function Documentation

## ◆ approx_convex_partition_2()

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::approx_convex_partition_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_2.h>`

computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into convex polygons.

The counterclockwise-oriented partition polygons are written to the sequence starting at position `result`. The past-the-end iterator for the resulting sequence of polygons is returned.

The number of convex polygons produced is no more than four times the minimal number.

Precondition
  The points in the range [`first`, `beyond`) define a simple counterclockwise-oriented polygon.

Requirements

1. `Traits` is a model of the concept `PartitionTraits_2` and, for the purposes of checking the postcondition that the partition produced is valid, it should also be a model of the concept `ConvexPartitionIsValidTraits_2`.
2. `std::iterator_traits<OutputIterator>::value_type` should be `Traits::Polygon_2`.
3. `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`, which should also be the type of the points stored in an object of type `Traits::Polygon_2`.
4. Points in the range `[first, beyond)` must define a simple polygon whose vertices are oriented counterclockwise.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator1>::value_type`.

See also
  `CGAL::convex_partition_is_valid_2()`
  `CGAL::greene_approx_convex_partition_2()`
  `CGAL::optimal_convex_partition_2()`
  `CGAL::partition_is_valid_2()`
  `CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>`
  `CGAL::y_monotone_partition_2()`

Implementation

This function implements the algorithm of Hertel and Mehlhorn [3] and is based on the class `Constrained_triangulation_2`. Given a triangulation of the polygon, the function requires \(O(n)\) time and space for a polygon with \( n\) vertices.

Example

The following program computes an approximately optimal convex partitioning of a polygon using the default traits class and stores the partition polygons in the list `partition_polys`.

File Partition_2/approx_convex_partition_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
void make_polygon(Polygon_2& polygon)
{
polygon.push_back(Point_2(391, 374));
polygon.push_back(Point_2(240, 431));
polygon.push_back(Point_2(252, 340));
polygon.push_back(Point_2(374, 320));
polygon.push_back(Point_2(289, 214));
polygon.push_back(Point_2(134, 390));
polygon.push_back(Point_2( 68, 186));
polygon.push_back(Point_2(154, 259));
polygon.push_back(Point_2(161, 107));
polygon.push_back(Point_2(435, 108));
polygon.push_back(Point_2(208, 148));
polygon.push_back(Point_2(295, 160));
polygon.push_back(Point_2(421, 212));
polygon.push_back(Point_2(441, 303));
}
int main()
{
Polygon_2 polygon;
Polygon_list partition_polys;
make_polygon(polygon);
CGAL::approx_convex_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
assert(CGAL::convex_partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(),
partition_polys.begin(),
partition_polys.end()));
return 0;
}
CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::Partition_traits_2
Traits class that can be used with all the 2-dimensional polygon partitioning algorithms.
Definition: Partition_traits_2.h:26
CGAL::Point_2
CGAL::Polygon_2
CGAL::Polygon_2::push_back
void push_back(const Point_2 &x)
CGAL::convex_partition_is_valid_2
bool convex_partition_is_valid_2(InputIterator point_first, InputIterator point_beyond, ForwardIterator poly_first, ForwardIterator poly_beyond, const Traits &traits=Default_traits)
determines if the polygons in the range [poly_first, poly_beyond) define a valid convex partition of ...
CGAL::approx_convex_partition_2
OutputIterator approx_convex_partition_2(InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
computes a partition of the polygon defined by the points in the range [first, beyond) into convex po...

Examples
  Partition_2/approx_convex_partition_2.cpp.

## ◆ convex_partition_is_valid_2()

template<class InputIterator , class ForwardIterator , class Traits >

bool CGAL::convex_partition_is_valid_2 | ( | InputIterator | point_first,
|  | InputIterator | point_beyond,
|  | ForwardIterator | poly_first,
|  | ForwardIterator | poly_beyond,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_is_valid_2.h>`

determines if the polygons in the range [`poly_first`, `poly_beyond`) define a valid convex partition of the polygon defined by the points in the range [`point_first`, `point_beyond`).

A convex partition is valid if the polygons do not overlap, the union of the polygons is the same as the original polygon given by the sequence of points, and if each partition polygon is convex. The function returns `true` iff the partition is valid and otherwise returns `false`.

Precondition
  The points in the range [`point_first`, `point_beyond`) define a simple, counterclockwise-oriented polygon.

Requires

- `Traits` is a model of the concept `ConvexPartitionIsValidTraits_2`.
- `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`, which should also be the type of the points stored in an object of type `Traits::Polygon_2`.
- `std::iterator_traits<ForwardIterator>::value_type` should be `Traits::Polygon_2`.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator>::value_type`.

See also
  `CGAL::approx_convex_partition_2()`
  `CGAL::greene_approx_convex_partition_2()`
  `CGAL::optimal_convex_partition_2()`
  `CGAL::partition_is_valid_2()`
  `CGAL::Is_convex_2`

Implementation

This function calls `partition_is_valid_2()` using the function object `Is_convex_2` to determine the convexity of each partition polygon. Thus the time required by this function is \(O(n \log n + e \log e)\) where \( n\) is the total number of vertices in the partition polygons and \( e\) the total number of edges.

Example

See the example presented with the function `approx_convex_partition_2()` for an illustration of the use of this function.

Examples
  Partition_2/approx_convex_partition_2.cpp, and Partition_2/greene_approx_convex_partition_2.cpp.

## ◆ greene_approx_convex_partition_2()

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::greene_approx_convex_partition_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_2.h>`

computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into convex polygons.

The counterclockwise-oriented partition polygons are written to the sequence starting at position `result`. The number of convex polygons produced is no more than four times the minimal number. The past-the-end iterator for the resulting sequence of polygons is returned.

Precondition
  The points in the range [`first`, `beyond`) define a simple, counterclockwise-oriented polygon.

Requirements

1. `Traits` is a model of the concepts `PartitionTraits_2`. For the purpose of checking the validity of the \( y\)-monotone partition produced as a preprocessing step for the convex partitioning, it must also be a model of `YMonotonePartitionIsValidTraits_2`. For the purpose of checking the postcondition that the convex partition is valid, `Traits` must also be a model of `ConvexPartitionIsValidTraits_2`.
2. `std::iterator_traits<OutputIterator>::value_type` is equivalent to `Traits::Polygon_2`.
3. `std::iterator_traits<InputIterator>::value_type` is equivalent to `Traits::Point_2`, which should also be equivalent to the type of the points stored in an object of type `Traits::Polygon_2`.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator>::value_type`.

See also
  `CGAL::approx_convex_partition_2()`
  `CGAL::convex_partition_is_valid_2()`
  `CGAL::optimal_convex_partition_2()`
  `CGAL::partition_is_valid_2()`
  `CGAL::y_monotone_partition_2()`

Implementation

This function implements the approximation algorithm of Greene [2] and requires \(O(n \log n)\) time and \(O(n)\) space to produce a convex partitioning given a \( y\)-monotone partitioning of a polygon with \( n\) vertices. The function `y_monotone_partition_2()` is used to produce the monotone partition.

Example

The following program computes an approximately optimal convex partitioning of a polygon using the default traits class and stores the partition polygons in the list `partition_polys`.

File Partition_2/greene_approx_convex_partition_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
void make_polygon(Polygon_2& polygon)
{
polygon.push_back(Point_2(391, 374));
polygon.push_back(Point_2(240, 431));
polygon.push_back(Point_2(252, 340));
polygon.push_back(Point_2(374, 320));
polygon.push_back(Point_2(289, 214));
polygon.push_back(Point_2(134, 390));
polygon.push_back(Point_2( 68, 186));
polygon.push_back(Point_2(154, 259));
polygon.push_back(Point_2(161, 107));
polygon.push_back(Point_2(435, 108));
polygon.push_back(Point_2(208, 148));
polygon.push_back(Point_2(295, 160));
polygon.push_back(Point_2(421, 212));
polygon.push_back(Point_2(441, 303));
}
int main()
{
Polygon_2 polygon;
Polygon_list partition_polys;
make_polygon(polygon);
CGAL::greene_approx_convex_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
assert(CGAL::convex_partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(),
partition_polys.begin(),
partition_polys.end()));
return 0;
}
CGAL::greene_approx_convex_partition_2
OutputIterator greene_approx_convex_partition_2(InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
computes a partition of the polygon defined by the points in the range [first, beyond) into convex po...

Examples
  Partition_2/greene_approx_convex_partition_2.cpp.

## ◆ is_y_monotone_2()

template<class InputIterator , class Traits >

bool CGAL::is_y_monotone_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | const Traits & | traits
| ) |  |

`#include <CGAL/is_y_monotone_2.h>`

determines if the sequence of points in the range [`first`, `beyond`) defines a \( y\)-monotone polygon or not.

If so, the function returns `true`, otherwise it returns `false`.

Requires

- `Traits` is a model of the concept `IsYMonotoneTraits_2`.
- `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`.

The default traits class `Default_traits` is the kernel in which the type `std::iterator_traits<InputIterator>::value_type` is defined.

See also
  `CGAL::Is_y_monotone_2<Traits>`
  `CGAL::y_monotone_partition_2()`
  `CGAL::y_monotone_partition_is_valid_2()`

Implementation

This function requires \(O(n)\) time for a polygon with \( n\) vertices.

Example

The following program computes a \( y\)-monotone partitioning of a polygon using the default traits class and stores the partition polygons in the list `partition_polys`. It then asserts that each of the partition polygons is, in fact, a \( y\)-monotone polygon and that the partition is valid. (Note that the assertions are superfluous unless the postcondition checking done by `y_monotone_partition_2()` has been turned off during compilation.)

File Partition_2/y_monotone_partition_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
void make_polygon(Polygon_2& polygon)
{
polygon.push_back(Point_2(391, 374));
polygon.push_back(Point_2(240, 431));
polygon.push_back(Point_2(252, 340));
polygon.push_back(Point_2(374, 320));
polygon.push_back(Point_2(289, 214));
polygon.push_back(Point_2(134, 390));
polygon.push_back(Point_2( 68, 186));
polygon.push_back(Point_2(154, 259));
polygon.push_back(Point_2(161, 107));
polygon.push_back(Point_2(435, 108));
polygon.push_back(Point_2(208, 148));
polygon.push_back(Point_2(295, 160));
polygon.push_back(Point_2(421, 212));
polygon.push_back(Point_2(441, 303));
}
int main( )
{
Polygon_2 polygon;
Polygon_list partition_polys;
make_polygon(polygon);
CGAL::y_monotone_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
std::list<Polygon_2>::const_iterator poly_it;
for (poly_it = partition_polys.begin(); poly_it != partition_polys.end();
poly_it++)
{
assert(CGAL::is_y_monotone_2((*poly_it).vertices_begin(),
(*poly_it).vertices_end()));
}
assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(),
partition_polys.begin(),
partition_polys.end()));
return 0;
}
CGAL::y_monotone_partition_2
OutputIterator y_monotone_partition_2(InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
computes a partition of the polygon defined by the points in the range [first, beyond) into -monotone...
CGAL::partition_is_valid_2
bool partition_is_valid_2(InputIterator point_first, InputIterator point_beyond, ForwardIterator poly_first, ForwardIterator poly_beyond, const Traits &traits=Default_traits)
returns true iff the polygons in the range [poly_first, poly_beyond) define a valid partition of the ...
CGAL::is_y_monotone_2
bool is_y_monotone_2(InputIterator first, InputIterator beyond, const Traits &traits)
determines if the sequence of points in the range [first, beyond) defines a -monotone polygon or not.

Examples
  Partition_2/y_monotone_partition_2.cpp.

## ◆ optimal_convex_partition_2()

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::optimal_convex_partition_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_2.h>`

computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into convex polygons.

The counterclockwise-oriented partition polygons are written to the sequence starting at position `result`. The number of convex polygons produced is minimal. The past-the-end iterator for the resulting sequence of polygons is returned.

Precondition
  The points in the range [`first`, `beyond`) define a simple, counterclockwise-oriented polygon.

Requirements

1. `Traits` is a model of the concept `OptimalConvexPartitionTraits_2`. For the purposes of checking the postcondition that the partition is valid, `Traits` should also be a model of `ConvexPartitionIsValidTraits_2`.

2. `std::iterator_traits<OutputIterator>::value_type` should be `Traits::Polygon_2`.
3. `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`, which should also be the type of the points stored in an object of type `Traits::Polygon_2`.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator>::value_type`.

See also
  `CGAL::approx_convex_partition_2()`
  `CGAL::convex_partition_is_valid_2()`
  `CGAL::greene_approx_convex_partition_2()`
  `CGAL::partition_is_valid_2()`
  `CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>`

Implementation

This function implements the dynamic programming algorithm of Greene [2], which requires \(O(n^4)\) time and \(O(n^3)\) space to produce a partitioning of a polygon with \( n\) vertices.

Example

The following program computes an optimal convex partitioning of a polygon using the default traits class and stores the partition polygons in the list `partition_polys`. It then asserts that the partition produced is valid. The traits class used for testing the validity is derived from the traits class used to produce the partition with the function object class `Is_convex_2` used to define the required `Is_valid` type. (Note that this assertion is superfluous unless the postcondition checking for `optimal_convex_partition_2()` has been turned off.)

File Partition_2/optimal_convex_partition_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Polygon_2 Polygon_2;
typedef Traits::Point_2 Point_2;
typedef std::list<Polygon_2> Polygon_list;
void make_polygon(Polygon_2& polygon)
{
polygon.push_back(Point_2(391, 374));
polygon.push_back(Point_2(240, 431));
polygon.push_back(Point_2(252, 340));
polygon.push_back(Point_2(374, 320));
polygon.push_back(Point_2(289, 214));
polygon.push_back(Point_2(134, 390));
polygon.push_back(Point_2( 68, 186));
polygon.push_back(Point_2(154, 259));
polygon.push_back(Point_2(161, 107));
polygon.push_back(Point_2(435, 108));
polygon.push_back(Point_2(208, 148));
polygon.push_back(Point_2(295, 160));
polygon.push_back(Point_2(421, 212));
polygon.push_back(Point_2(441, 303));
}
int main()
{
Polygon_2 polygon;
Polygon_list partition_polys;
make_polygon(polygon);
CGAL::optimal_convex_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(),
partition_polys.begin(),
partition_polys.end()));
return 0;
}
CGAL::optimal_convex_partition_2
OutputIterator optimal_convex_partition_2(InputIterator first, InputIterator beyond, OutputIterator result, const Traits &traits=Default_traits)
computes a partition of the polygon defined by the points in the range [first, beyond) into convex po...

Examples
  Partition_2/optimal_convex_partition_2.cpp.

## ◆ partition_is_valid_2()

template<class InputIterator , class ForwardIterator , class Traits >

bool CGAL::partition_is_valid_2 | ( | InputIterator | point_first,
|  | InputIterator | point_beyond,
|  | ForwardIterator | poly_first,
|  | ForwardIterator | poly_beyond,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_is_valid_2.h>`

returns `true` iff the polygons in the range [`poly_first`, `poly_beyond`) define a valid partition of the polygon defined by the points in the range [`point_first`, `point_beyond`) and `false` otherwise.

A valid partition is one in which the polygons are nonoverlapping and the union of the polygons is the same as the original polygon. Each polygon must also satisfy the property tested by `Traits::Is_valid()`.

Precondition
  The points in the range [`point_first`, `point_beyond`) define a simple, counterclockwise-oriented polygon.

Requires

- `Traits` is a model of the concept `PartitionIsValidTraits_2` and the concept defining the requirements for the validity test implemented by `Traits::Is_valid()`.
- `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`, which should also be the type of the points stored in an object of type `Traits::Polygon_2`.
- `std::iterator_traits<ForwardIterator>::value_type` should be `Traits::Polygon_2`.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator>::value_type`.

See also
  `CGAL::approx_convex_partition_2()`
  `CGAL::greene_approx_convex_partition_2()`
  `CGAL::is_y_monotone_2()`
  `CGAL::optimal_convex_partition_2()`
  `CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>`
  `CGAL::y_monotone_partition_2()`
  `CGAL::Is_convex_2`

Implementation

This function requires \(O(n \log n + e \log e + \Sigma_{i=1}^p m_i)\) where \( n\) is the total number of vertices of the \( p\) partition polygons, \( e\) is the total number of edges of the partition polygons and \( m_i\) is the time required by `Traits::Is_valid()` to test if partition polygon \( p_i\) is valid.

Example

See the example presented with the function `optimal_convex_partition_2()` for an illustration of the use of this function.

Examples
  Partition_2/optimal_convex_partition_2.cpp, Partition_2/y_monotone_partition_2.cpp, and Partition_2/y_monotone_partition_indices_2.cpp.

## ◆ y_monotone_partition_2()

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::y_monotone_partition_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_2.h>`

computes a partition of the polygon defined by the points in the range [`first`, `beyond`) into \( y\)-monotone polygons.

The counterclockwise-oriented partition polygons are written to the sequence starting at position `result`. The past-the-end iterator for the resulting sequence of polygons is returned.

Precondition
  The points in the range [`first`, `beyond`) define a simple, counterclockwise-oriented polygon.

Requirements

1. `Traits` is a model of the concept `PartitionTraits_2` and, for the purposes of checking the postcondition that the partition is valid, it should also be a model of `YMonotonePartitionIsValidTraits_2`.
2. `std::iterator_traits<OutputIterator>::value_type` should be `Traits::Polygon_2`.
3. `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`, which should also be the type of the points stored in an object of type `Traits::Polygon_2`.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator>::value_type`.

See also
  `CGAL::approx_convex_partition_2()`
  `CGAL::greene_approx_convex_partition_2()`
  `CGAL::optimal_convex_partition_2()`
  `CGAL::partition_is_valid_2()`
  `CGAL::y_monotone_partition_is_valid_2()`

Implementation

This function implements the algorithm presented by de Berg et al. [1] which requires \(O(n \log n)\) time and \(O(n)\) space for a polygon with \( n\) vertices.

Example

The following program computes a \( y\)-monotone partitioning of a polygon using the default traits class and stores the partition polygons in the list `partition_polys`. It then asserts that each partition polygon produced is, in fact, \( y\)-monotone and that the partition is valid. (Note that these assertions are superfluous unless the postcondition checking for `y_monotone_partition_2()` has been turned off.)

File Partition_2/y_monotone_partition_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K> Traits;
typedef Traits::Point_2 Point_2;
typedef Traits::Polygon_2 Polygon_2;
typedef std::list<Polygon_2> Polygon_list;
void make_polygon(Polygon_2& polygon)
{
polygon.push_back(Point_2(391, 374));
polygon.push_back(Point_2(240, 431));
polygon.push_back(Point_2(252, 340));
polygon.push_back(Point_2(374, 320));
polygon.push_back(Point_2(289, 214));
polygon.push_back(Point_2(134, 390));
polygon.push_back(Point_2( 68, 186));
polygon.push_back(Point_2(154, 259));
polygon.push_back(Point_2(161, 107));
polygon.push_back(Point_2(435, 108));
polygon.push_back(Point_2(208, 148));
polygon.push_back(Point_2(295, 160));
polygon.push_back(Point_2(421, 212));
polygon.push_back(Point_2(441, 303));
}
int main( )
{
Polygon_2 polygon;
Polygon_list partition_polys;
make_polygon(polygon);
CGAL::y_monotone_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys));
std::list<Polygon_2>::const_iterator poly_it;
for (poly_it = partition_polys.begin(); poly_it != partition_polys.end();
poly_it++)
{
assert(CGAL::is_y_monotone_2((*poly_it).vertices_begin(),
(*poly_it).vertices_end()));
}
assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(),
partition_polys.begin(),
partition_polys.end()));
return 0;
}

Examples
  Partition_2/y_monotone_partition_2.cpp, and Partition_2/y_monotone_partition_indices_2.cpp.

## ◆ y_monotone_partition_is_valid_2()

template<class InputIterator , class ForwardIterator , class Traits >

bool CGAL::y_monotone_partition_is_valid_2 | ( | InputIterator | point_first,
|  | InputIterator | point_beyond,
|  | ForwardIterator | poly_first,
|  | ForwardIterator | poly_beyond,
|  | const Traits & | traits = `Default_traits`
| ) |  |

`#include <CGAL/partition_is_valid_2.h>`

determines if the polygons in the range [`poly_first`, `poly_beyond`) define a valid \( y\)-monotone partition of the simple, counterclockwise-oriented polygon represented by the points in the range [`point_first`, `point_beyond`).

A valid partition is one in which the polygons are nonoverlapping and the union of the polygons is the same as the original polygon and each polygon is \( y\)-monotone

The function returns `true` iff the partition is valid and otherwise returns `false`.

Requires

- `Traits` is a model of the concept `YMonotonePartitionIsValidTraits_2`.
- `std::iterator_traits<InputIterator>::value_type` should be `Traits::Point_2`, which should also be the type of the points stored in an object of type `Traits::Polygon_2`.
- `std::iterator_traits<ForwardIterator>::value_type` should be `Traits::Polygon_2`.

The default traits class `Default_traits` is `Partition_traits_2`, with the representation type determined by `std::iterator_traits<InputIterator>::value_type`.

See also
  `CGAL::y_monotone_partition_2()`
  `CGAL::is_y_monotone_2()`
  `CGAL::partition_is_valid_2()`
  `CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>`

Implementation

This function uses the function `partition_is_valid_2()` together with the function object `Is_y_monotone_2` to determine if each polygon is \( y\)-monotone or not. Thus the time required is \(O(n \log n + e \log e)\) where \( n\) is the total number of vertices of the partition polygons and \( e\) is the total number of edges.

Example

See the example presented with the function `y_monotone_partition_2()` for an illustration of the use of this function.