2D Polygon Partitioning Reference

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-22b
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 assertion flags for this package use PARTITION in their names (e.g., CGAL_PARTITION_NO_POSTCONDITIONS). 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. More...
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. More...
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. More...
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. More...
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. More...
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). More...
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. More...
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). More...

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;
}

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;
}

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;
}

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;
}

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.