CGAL::Hertel_Mehlhorn_convex_decomposition_2< Kernel, Container > Class Template Reference

#include <CGAL/Polygon_convex_decomposition_2.h>

Definition

The Hertel_Mehlhorn_convex_decomposition_2 class implements the approximation algorithm of Hertel and Mehlhorn for decomposing a polygon into convex sub-polygons [8].

This algorithm constructs a triangulation of the input polygon and proceeds by removing unnecessary triangulation edges. Given the triangulation, the algorithm requires \( O(n)\) time and space to construct a convex decomposition (where \( n\) is the size of the input polygon), whose size is guaranteed to be no more than four times the size of the optimal decomposition.

Template Parameters

Kernel	must be a geometric kernel that can be used for the polygon.
Container	must be a container that can be used for the polygon. It is by default std::vector<typename Kernel::Point_2>.

Is Model Of:

PolygonConvexDecomposition_2

See also

CGAL::approx_convex_partition_2()

Public Types
typedef CGAL::Polygon_2< Kernel, Container >	Polygon_2