CGAL::y_monotone_partition_2

Definition

Function that produces a set of $$y-monotone polygons that represent a partitioning of a polygon defined on a sequence of points.

#include <CGAL/partition_2.h>

template <class InputIterator, class OutputIterator, class Traits>
OutputIterator	y_monotone_partition_2 ( InputIterator first, InputIterator beyond, OutputIterator result, Traits traits = Default_traits)
		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 YMonotonePartitionTraits_2 and, for the purposes of checking the postcondition that the partition is valid, it should also be a model of YMonotonePartitionIsValidTraits_2.
2. OutputIterator::value_type should be Traits::Polygon_2.
3. 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 InputIterator::value_type.

See Also

Implementation

This function implements the algorithm presented by de Berg et al. [dBvKOS97] 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: examples/Partition_2/y_monotone_ex.C

#include <CGAL/basic.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_polygon_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;
typedef CGAL::Creator_uniform_2<int, Point_2>               Creator;
typedef CGAL::Random_points_in_square_2<Point_2, Creator>   Point_generator;

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;

/*
   CGAL::random_polygon_2(50, std::back_inserter(polygon), 
                          Point_generator(100));
*/
   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;
}