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>
The default traits class Default_traits is Partition_traits_2, with the representation type determined by InputIterator::value_type.
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.cpp
#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; }