CGAL::Greene_convex_decomposition_2<Kernel,Container>

Definition

The Greene_convex_decomposition_2<Kernel,Container> class implements the approximation algorithm of Greene for the decomposition of an input polygon into convex sub-polygons [Gre83]. This algorithm takes $$O(n log$$n) time and $$O(n) space, where $$n is the size of the input polygon, and outputs a decomposition whose size is guaranteed to be no more than four times the size of the optimal decomposition.

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