\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.13 - 2D Minkowski Sums
CGAL::Hertel_Mehlhorn_convex_decomposition_2< Kernel, Container > Class Template Reference

#include <CGAL/Polygon_convex_decomposition_2.h>


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
Kernelmust be a geometric kernel that can be used for the polygon.
Containermust be a container that can be used for the polygon. It is by default std::vector<typename Kernel::Point_2>.
Is Model Of:
See also

Public Types

typedef CGAL::Polygon_2< Kernel, Container > Polygon_2