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

#include <CGAL/Polygon_convex_decomposition_2.h>

Definition

template<typename Kernel, typename Container>
class CGAL::Hertel_Mehlhorn_convex_decomposition_2< Kernel, Container >

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