CGAL::Optimal_convex_decomposition_2<Kernel,Container>

Definition

The Optimal_convex_decomposition_2<Kernel,Container> class provides an implementation of Greene's dynamic programming algorithm for optimal decomposition of a polygon into convex sub-polygons [Gre83]. Note that this algorithm requires O(n⁴) time and O(n³) space in the worst case, where n is the size of the input polygon.

The Polygon_2 type defined by the class is simply Polygon_2<Kernel,Container>. The Container parameter is by default std::vector<typename Kernel::Point_2>.

#include <CGAL/Polygon_convex_decomposition_2.h>

Is Model for the Concepts

See Also