\( \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.12 - 2D Minkowski Sums
CGAL::Small_side_angle_bisector_decomposition_2< Kernel, Container > Class Template Reference
2D Minkowski Sums Reference

#include <CGAL/Small_side_angle_bisector_decomposition_2.h>

Definition

The Small_side_angle_bisector_decomposition_2 class implements a simple yet efficient heuristic for decomposing an input polygon into convex sub-polygons.

It is based on the algorithm suggested by Flato and Halperin [5], but without introducing Steiner points. The algorithm operates in two major steps. In the first step, it tries to subdivide the polygon by connect two reflex vertices with an edge. When this is not possible any more, it eliminates the reflex vertices one by one by connecting them to other convex vertices, such that the new edge best approximates the angle bisector of the reflex vertex. The algorithm operates in \( O(n^2)\) time and takes \( O(n)\) space at the worst case, where \( n\) is the size of the input polygon.

Is Model Of:
PolygonConvexDecomposition_2
Examples:
Minkowski_sum_2/sum_by_decomposition.cpp.