CGAL::optimal_convex_partition_2

Function that produces a set of convex polygons that represent a partitioning of a polygon defined on a sequence of points. The number of convex polygons produced is minimal.

#include <CGAL/partition_2.h>

template <class InputIterator, class OutputIterator, class Traits>
OutputIterator	optimal_convex_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 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. 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. 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

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 CGAL::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: examples/Partition_2/optimal_convex_partition_2.C

#include <CGAL/basic.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/Partition_is_valid_traits_2.h>
#include <CGAL/polygon_function_objects.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 CGAL::Is_convex_2<Traits>                           Is_convex_2;
typedef Traits::Polygon_2                                   Polygon_2;
typedef Traits::Point_2                                     Point_2;
typedef Polygon_2::Vertex_const_iterator                    Vertex_iterator;
typedef std::list<Polygon_2>                                Polygon_list;
typedef CGAL::Partition_is_valid_traits_2<Traits, Is_convex_2>
                                                            Validity_traits;
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;
   Traits                partition_traits;
   Validity_traits       validity_traits;

/*
   CGAL::random_polygon_2(50, std::back_inserter(polygon), 
                          Point_generator(100));
*/
   make_polygon(polygon);
   CGAL::optimal_convex_partition_2(polygon.vertices_begin(), 
                                    polygon.vertices_end(),
                                    std::back_inserter(partition_polys),
                                    partition_traits);
   assert(CGAL::partition_is_valid_2(polygon.vertices_begin(), 
                                     polygon.vertices_end(),
                                     partition_polys.begin(), 
                                     partition_polys.end(),
                                     validity_traits));
   return 0;
}