CGAL 6.1.1 - 2D Minkowski Sums

Loading...
Searching...
No Matches
CGAL::Small_side_angle_bisector_decomposition_2< Kernel, Container > Class Template Reference
Reference Manual

`#include <CGAL/Small_side_angle_bisector_decomposition_2.h>`

## Definition

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

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.