\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.14 - 2D Polygon Partitioning
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::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;
Validity_traits;
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;
}