|
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>