\( \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.11 - 2D Minkowski Sums
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules | Classes | Functions
2D Minkowski Sums Reference

Minkowski_sum_2.png
Ron Wein, Alon Baram, Eyal Flato, Efi Fogel, Michael Hemmer, Sebastian Morr
This package consists of functions that compute the Minkowski sum of two simple straight-edge polygons in the plane. It also contains functions for computing the Minkowski sum of a polygon and a disc, an operation known as offsetting or dilating a polygon. The package can compute the exact representation of the offset polygon, or provide a guaranteed approximation of the offset.


Introduced in: CGAL 3.3
Depends on: 2D Arrangements, 3D Fast Intersection and Distance Computation, 2D Triangulation
BibTeX: cgal:w-rms2-17b
License: GPL

This package consist of functions for computing the Minkowksi sum of two polygons in the plane. Namely, given two polygons \( P,Q \in \mathbb{R}^2\) it computes \( P \oplus Q = \left\{ p + q ~|~ p \in P, q \in Q \right\}\).

In addition, the package also includes functions for offsetting a polygon, namely computing its Minkowski sum with a disc of a given radius, and for insetting a polygon (namely computing its inner offset). It is possible to compute the exact representation of the offset (or the inset), or to approximate it with guaranteed error bounds, in order to speed up the computation time.

Classified Reference Pages

Functions

Concepts

Classes

Modules

 Concepts
 

Classes

class  CGAL::Greene_convex_decomposition_2< Kernel, Container >
 The Greene_convex_decomposition_2 class implements the approximation algorithm of Greene for the decomposition of an input polygon into convex sub-polygons. More...
 
class  CGAL::Optimal_convex_decomposition_2< Kernel, Container >
 The Optimal_convex_decomposition_2 class provides an implementation of Greene's dynamic programming algorithm for optimal decomposition of a polygon into convex sub-polygons. More...
 
class  CGAL::Polygon_nop_decomposition_2< Kernel, Container >
 The Polygon_nop_decomposition_2 class implements a convex decomposition of a polygon, which merely passes the input polygon to the list of output convex polygons. More...
 
class  CGAL::Polygon_triangulation_decomposition_2< Kernel, Container >
 The Polygon_triangulation_decomposition_2 class implements a convex decomposition of a polygon or a polygon with holes into triangles using the Delaunay constrained triangulation functionality of the 2D Triangulation package. More...
 
class  CGAL::Polygon_vertical_decomposition_2< Kernel, Container >
 The Polygon_vertical_decomposition_2 class implements a convex decompistion of a polygon or a polygon with holes into pseudo trapezoids utilizing the CGAL::decompose() free function of the 2D Arrangements package. More...
 
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. More...
 

Functions

template<class Kernel , class Container , class OutputIterator >
OutputIterator CGAL::approximated_inset_2 (const Polygon_2< Kernel, Container > &pgn, const typename Kernel::FT &r, const double &eps, OutputIterator oi)
 Provides a guaranteed approximation of the inset, or inner offset, of the given polygon P by a given radius r. More...
 
template<class Kernel , class Container >
Gps_circle_segment_traits_2
< Kernel >
::Polygon_with_holes_2 		CGAL::approximated_offset_2 (const Polygon_2< Kernel, Container > &P, const typename Kernel::FT &r, const double &eps)
 Provides a guaranteed approximation of the offset of the given polygon P by a given radius r - namely, the function computes the Minkowski sum \( P \oplus B_r\), where \( B_r\) is a disc of radius r centered at the origin. More...
 
template<class Kernel , class Container >
Gps_circle_segment_traits_2
< Kernel >
::Polygon_with_holes_2 		CGAL::approximated_offset_2 (const Polygon_with_holes_2< Kernel, Container > &wh, const typename Kernel::FT &r, const double &eps)
 Provides a guaranteed approximation of offset the given polygon with holes pwh by a given radius r, such that the approximation error is bounded by eps. More...
 
template<class Kernel , class Container , class DecompositionStrategy >
Gps_circle_segment_traits_2
< Kernel >
::Polygon_with_holes_2 		CGAL::approximated_offset_2 (const Polygon_2< Kernel, Container > &P, const typename Kernel::FT &r, const double &eps, const DecompositionStrategy &decomp)
 Provides a guaranteed approximation of the offset of the given polygon P by a radius r, as described above. More...
 
template<typename Kernel , typename Container >
Polygon_with_holes_2< Kernel,
Container > 		CGAL::minkowski_sum_2 (const PolygonType1< Kernel, Container > &P, const PolygonType2< Kernel, Container > &Q)
 Computes the Minkowski sum \( P \oplus Q\) of two given polygons (which may have holes). More...
 
template<typename Kernel , typename Container >
Polygon_with_holes_2< Kernel,
Container > 		CGAL::minkowski_sum_by_reduced_convolution_2 (const PolygonType1< Kernel, Container > &P, const PolygonType2< Kernel, Container > &Q)
 Computes the Minkowski sum \( P \oplus Q\) of the two given polygons. More...
 
template<typename Kernel , typename Container >
Polygon_with_holes_2< Kernel,
Container > 		CGAL::minkowski_sum_by_full_convolution_2 (const Polygon_2< Kernel, Container > &P, const Polygon_2< Kernel, Container > &Q)
 Computes the Minkowski sum \( P \oplus Q\) of the two given polygons. More...
 
template<typename Kernel , typename Container , typename PolygonConvexDecompositionP_2_ , typename PolygonConvexDecompositionQ_2_ >
Polygon_with_holes_2< Kernel,
Container > 		CGAL::minkowski_sum_2 (const PolygonType1< Kernel, Container > &P, const PolygonType2< Kernel, Container > &Q, const PolygonConvexDecompositionP_2_ &decomp_P, const PolygonConvexDecompositionQ_2_ &decomp_Q, const Gps_segment_traits_2 &traits=Gps_segment_traits_2< Kernel, Container, Arr_segment_traits >())
 Computes the Minkowski sum \( P \oplus Q\) of the two given polygons. More...
 
template<typename Kernel , typename Container , typename PolygonConvexDecomposition_2_ >
Polygon_with_holes_2< Kernel,
Container > 		CGAL::minkowski_sum_2 (const PolygonType1< Kernel, Container > &P, const PolygonType2< Kernel, Container > &Q, const PolygonConvexDecomposition_2_ &decomp, const Gps_segment_traits_2 &traits=Gps_segment_traits_2< Kernel, Container, Arr_segment_traits >())
 Computes the Minkowski sum \( P \oplus Q\) of the two given polygons. More...
 
template<typename Kernel , typename Container , typename PolygonNoHolesConvexDecomposition_2_ , typename PolygonWithHolesConvexDecomposition_2_ >
Polygon_with_holes_2< Kernel,
Container > 		CGAL::minkowski_sum_by_decomposition_2 (const PolygonType1< Kernel, Container > &P, const PolygonType2< Kernel, Container > &Q, const PolygonNoHolesConvexDecomposition_2_ &no_holes_decomp, const PolygonWithHolesConvexDecomposition_2_ &with_holes_decomp, const Gps_segment_traits_2 &traits=Gps_segment_traits_2< Kernel, Container, Arr_segment_traits >())
 Computes the Minkowski sum \( P \oplus Q\) of the two given polygons using the decomposition strategy. More...
 
template<class ConicTraits , class Container , class OutputIterator >
OutputIterator CGAL::inset_polygon_2 (const Polygon_2< typename ConicTraits::Rat_kernel, Container > &P, const typename ConicTraits::Rat_kernel::FT &r, const ConicTraits &traits, OutputIterator oi)
 Computes the inset, or inner offset, of the given polygon P by a given radius r - namely, the function computes the set of points inside the polygon whose distance from \( P\)'s boundary is at least \( r\): \( \{ p \in P \;|\; {\rm dist}(p, \partial P) \geq r \}\). More...
 
template<class ConicTraits , class Container >
Gps_traits_2< ConicTraits >
::Polygon_with_holes_2 		CGAL::offset_polygon_2 (const Polygon_2< typename ConicTraits::Rat_kernel, Container > &P, const typename ConicTraits::Rat_kernel::FT &r, const ConicTraits &traits)
 Computes the offset of the given polygon P by a given radius r - namely, the function computes the Minkowski sum \( P \oplus B_r\), where \( B_r\) is a disc of radius r centered at the origin. More...
 
template<class ConicTraits , class Container >
Gps_traits_2< ConicTraits >
::Polygon_with_holes_2 		CGAL::offset_polygon_2 (const Polygon_with_holes_2< typename ConicTraits::Rat_kernel, Container > &pwh, const typename ConicTraits::Rat_kernel::FT &r, const ConicTraits &traits)
 Computes the offset of the given polygon with holes pwh by a given radius r. More...
 
template<class ConicTraits , class Container , class DecompositionStrategy >
Gps_traits_2< ConicTraits >
::Polygon_with_holes_2 		CGAL::offset_polygon_2 (const Polygon_2< typename ConicTraits::Rat_kernel, Container > &P, const typename ConicTraits::Rat_kernel::FT &r, const DecompositionStrategy &decomp, const ConicTraits &traits)
 Computes the exact representation of the offset of the given polygon P by a radius r, as described above. More...
 

Function Documentation

template<class Kernel , class Container , class OutputIterator >
OutputIterator CGAL::approximated_inset_2 ( const Polygon_2< Kernel, Container > &  pgn,
const typename Kernel::FT &  r,
const double &  eps,
OutputIterator  oi 
)

Provides a guaranteed approximation of the inset, or inner offset, of the given polygon P by a given radius r.

Namely, the function computes the set of points inside the polygon whose distance from \( P\)'s boundary is at least \( r\): \( \{ p \in P \;|\; {\rm dist}(p, \partial P) \geq r \}\), with the approximation error bounded by eps. Note that as the input polygon may not be convex, its inset may comprise several disconnected components. The result is therefore represented as a sequence of generalized polygons, whose edges are either line segments or circular arcs. The output sequence is returned via the output iterator oi, whose value-type must be Gps_circle_segment_traits_2::Polygon_2.

Precondition
P is a simple polygon.

#include <CGAL/approximated_offset_2.h>

Examples:
Minkowski_sum_2/approx_inset.cpp.
template<class Kernel , class Container >
Gps_circle_segment_traits_2<Kernel>::Polygon_with_holes_2 CGAL::approximated_offset_2 ( const Polygon_2< Kernel, Container > &  P,
const typename Kernel::FT &  r,
const double &  eps 
)

Provides a guaranteed approximation of the offset of the given polygon P by a given radius r - namely, the function computes the Minkowski sum \( P \oplus B_r\), where \( B_r\) is a disc of radius r centered at the origin.

The function actually outputs a set \( S\) that contains the Minkowski sum, such that the approximation error is bounded by eps. Note that as the input polygon may not be convex, its offset may not be a simple polygon. The result is therefore represented as a polygon with holes, whose edges are either line segments or circular arcs.

Precondition
P is a simple polygon.

#include <CGAL/approximated_offset_2.h>

Examples:
Minkowski_sum_2/approx_offset.cpp.
template<class Kernel , class Container >
Gps_circle_segment_traits_2<Kernel>::Polygon_with_holes_2 CGAL::approximated_offset_2 ( const Polygon_with_holes_2< Kernel, Container > &  wh,
const typename Kernel::FT &  r,
const double &  eps 
)

Provides a guaranteed approximation of offset the given polygon with holes pwh by a given radius r, such that the approximation error is bounded by eps.

It does so by offsetting outer boundary of pwh and insetting its holes. The result is represented as a generalized polygon with holes, such that the edges of the polygon correspond to line segment and circular arcs.

Precondition
pwh is not unbounded (it has a valid outer boundary).

#include <CGAL/approximated_offset_2.h>

template<class Kernel , class Container , class DecompositionStrategy >
Gps_circle_segment_traits_2<Kernel>::Polygon_with_holes_2 CGAL::approximated_offset_2 ( const Polygon_2< Kernel, Container > &  P,
const typename Kernel::FT &  r,
const double &  eps,
const DecompositionStrategy &  decomp 
)

Provides a guaranteed approximation of the offset of the given polygon P by a radius r, as described above.

If the input polygon P is not convex, the function decomposes it into convex sub-polygons \( P_1, \ldots, P_k\) and computes the union of the sub-offsets (namely \( \bigcup_{i}{(P_i \oplus B_r)}\)). The decomposition is performed using the given decomposition strategy decomp, which must be an instance of a class that models the concept PolygonConvexDecomposition.

Precondition
P is a simple polygon.

#include <CGAL/approximated_offset_2.h>

template<class ConicTraits , class Container , class OutputIterator >
OutputIterator CGAL::inset_polygon_2 ( const Polygon_2< typename ConicTraits::Rat_kernel, Container > &  P,
const typename ConicTraits::Rat_kernel::FT &  r,
const ConicTraits &  traits,
OutputIterator  oi 
)

Computes the inset, or inner offset, of the given polygon P by a given radius r - namely, the function computes the set of points inside the polygon whose distance from \( P\)'s boundary is at least \( r\): \( \{ p \in P \;|\; {\rm dist}(p, \partial P) \geq r \}\).

Note that as the input polygon may not be convex, its inset may comprise several disconnected components. The result is therefore represented as a sequence of generalized polygons, such that the edges of each polygon correspond to line segments and circular arcs, both are special types of conic arcs, as represented by the traits class. The output sequence is returned via the output iterator oi, whose value-type must be Gps_traits_2::Polygon_2.

Precondition
P is a simple polygon.

#include <CGAL/offset_polygon_2.h>

Examples:
Minkowski_sum_2/exact_inset.cpp.
template<typename Kernel , typename Container >
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_2 ( const PolygonType1< Kernel, Container > &  P,
const PolygonType2< Kernel, Container > &  Q 
)

Computes the Minkowski sum \( P \oplus Q\) of two given polygons (which may have holes).

PolygonType1 and PolygonType2 can be any combination of:

This method defaults to the reduced convolution method, see below.

See Also
CGAL::minkowski_sum_by_reduced_convolution_2()
CGAL::minkowski_sum_by_full_convolution_2()

#include <CGAL/minkowski_sum_2.h>

Examples:
Minkowski_sum_2/sum_by_decomposition.cpp, Minkowski_sum_2/sum_triangle_square.cpp, and Minkowski_sum_2/sum_with_holes.cpp.
template<typename Kernel , typename Container , typename PolygonConvexDecompositionP_2_ , typename PolygonConvexDecompositionQ_2_ >
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_2 ( const PolygonType1< Kernel, Container > &  P,
const PolygonType2< Kernel, Container > &  Q,
const PolygonConvexDecompositionP_2_ &  decomp_P,
const PolygonConvexDecompositionQ_2_ &  decomp_Q,
const Gps_segment_traits_2 &  traits = Gps_segment_traits_2< Kernel, Container, Arr_segment_traits >() 
)

Computes the Minkowski sum \( P \oplus Q\) of the two given polygons.

The function decomposes the summand P into convex sub-polygons \( P_1, \ldots, P_k\) using the given decomposition method decomp_P. If the summand P is of type Polygon_2, then decomp_P must be an instance of a class template that models the concept PolygonConvexDecomposition_2. If P is of type Polygon_with_holes_2, then decomp_P must be an instance of a class template that models the concept PolygonWithHolesConvexDecomposition_2. Similarly, the function decomposes the summand Q into convex sub-polygons \( Q_1, \ldots, Q_k\) using the given decomposition method decomp_Q. If the summand Q is of type Polygon_2, then decomp_Q must be an instance of a class template that models the concept PolygonConvexDecomposition_2. If Q is of type Polygon_with_holes_2, then decomp_Q must be an instance of a class template that models the concept PolygonWithHolesConvexDecomposition_2. Then, the function computes the union of pairwise sub-sums (namely \( \bigcup_{i,j}{(P_i \oplus Q_j)}\)).

#include <CGAL/minkowski_sum_2.h>

template<typename Kernel , typename Container , typename PolygonConvexDecomposition_2_ >
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_2 ( const PolygonType1< Kernel, Container > &  P,
const PolygonType2< Kernel, Container > &  Q,
const PolygonConvexDecomposition_2_ &  decomp,
const Gps_segment_traits_2 &  traits = Gps_segment_traits_2< Kernel, Container, Arr_segment_traits >() 
)

Computes the Minkowski sum \( P \oplus Q\) of the two given polygons.

The function decomposes the summands P and Q into convex sub-polygons \( P_1, \ldots, P_k\) and \( Q_1, \ldots, Q_{\ell}\), respectively. Then, it computes the union of pairwise sub-sums (namely \( \bigcup_{i,j}{(P_i \oplus Q_j)}\)). The decomposition is performed using the given decomposition method decomp. If both summands \( P \oplus Q\) are of type Polygon_2, then decomp must be instance of a class template that models the concept PolygonConvexDecomposition_2. If both summands are of type Polygon_with_holes_2, then decomp must be a model of the concept PolygonWithHolesConvexDecomposition_2.

#include <CGAL/minkowski_sum_2.h>

template<typename Kernel , typename Container , typename PolygonNoHolesConvexDecomposition_2_ , typename PolygonWithHolesConvexDecomposition_2_ >
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_by_decomposition_2 ( const PolygonType1< Kernel, Container > &  P,
const PolygonType2< Kernel, Container > &  Q,
const PolygonNoHolesConvexDecomposition_2_ &  no_holes_decomp,
const PolygonWithHolesConvexDecomposition_2_ &  with_holes_decomp,
const Gps_segment_traits_2 &  traits = Gps_segment_traits_2< Kernel, Container, Arr_segment_traits >() 
)

Computes the Minkowski sum \( P \oplus Q\) of the two given polygons using the decomposition strategy.

It decomposes the summands P and Q into convex sub-polygons \( P_1, \ldots, P_k\) and \( Q_1, \ldots, Q_{\ell}\), respectively. Then, it computes the union of pairwise sub-sums (namely \( \bigcup_{i,j}{(P_i \oplus Q_j)}\)).

If the summand P is of type Polygon_with_holes_2, then the function first applies the hole filteration on P. If the summand P remains a polygon with holes, then the function decomposes the summand P using the given decomposition method with_holes_decomp. If, however, P turns into a polygon without holes, then the function decomposes the summand P using the given decomposition method no_holes_decomp, unless the result is a convex polygon, in which case the nop strategy is applied; namely, an instance of the class template Polygon_nop_decomposition_2 is used. If P is a polygon without holes to start with, then only convexity is checked (checking whether the result is convex inccurs a small overhead though). Then depending on the result either no_holes_decomp or the nop strategy is applied. Similarly, if the summand Q is of type Polygon_with_holes_2, then the function first applies the hole filteration on Q. If the summand Q remains a polygon with holes, then the function decomposes the summand Q using the given decomposition method with_holes_decomp. If, however, Q turns into a polygon without holes, then the function decomposes the summand Q using the given decomposition method no_holes_decomp, unless the result is a convex polygon, in which case the nop strategy is applied. If Q is a polygon without holes to start with, then only convexity is checked and the decomposition strategy is chosen accordingly.

Template Parameters
PolygonNoHolesConvexDecomposition_2_a model of the concept PolygonConvexDecomposition_2.
PolygonWithHolesConvexDecomposition_2_a model of the concept PolygonWithHolesConvexDecomposition_2.

#include <CGAL/minkowski_sum_2.h>

template<typename Kernel , typename Container >
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_by_full_convolution_2 ( const Polygon_2< Kernel, Container > &  P,
const Polygon_2< Kernel, Container > &  Q 
)

Computes the Minkowski sum \( P \oplus Q\) of the two given polygons.

The function computes the (full) convolution cycles of the two polygons and extract the regions having positive winding number with respect to these cycles. This method work very efficiently, regardless of whether P and Q are convex or non-convex.

PolygonType1 and PolygonType2 can be any combination of:

#include <CGAL/minkowski_sum_2.h>

template<typename Kernel , typename Container >
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_by_reduced_convolution_2 ( const PolygonType1< Kernel, Container > &  P,
const PolygonType2< Kernel, Container > &  Q 
)

Computes the Minkowski sum \( P \oplus Q\) of the two given polygons.

The function computes the reduced convolution [3] of the two polygons and extracts those loops of the convolution that are part of the Minkowsi sum. This method works very efficiently, regardless of whether P and Q are convex or non-convex. In general, it is more efficient than the full convolution method, except for degenerate cases where the output polygon has many holes.

PolygonType1 and PolygonType2 can be any combination of:

#include <CGAL/minkowski_sum_2.h>

template<class ConicTraits , class Container >
Gps_traits_2<ConicTraits>::Polygon_with_holes_2 CGAL::offset_polygon_2 ( const Polygon_2< typename ConicTraits::Rat_kernel, Container > &  P,
const typename ConicTraits::Rat_kernel::FT &  r,
const ConicTraits &  traits 
)

Computes the offset of the given polygon P by a given radius r - namely, the function computes the Minkowski sum \( P \oplus B_r\), where \( B_r\) is a disc of radius r centered at the origin.

Note that as the input polygon may not be convex, its offset may not be a simple polygon. The result is therefore represented as a generalized polygon with holes, such that the edges of the polygon correspond to line segments and circular arcs, both are special types of conic arcs, as represented by the traits class.

Precondition
P is a simple polygon.

#include <CGAL/offset_polygon_2.h>

Examples:
Minkowski_sum_2/exact_offset.cpp.
template<class ConicTraits , class Container >
Gps_traits_2<ConicTraits>::Polygon_with_holes_2 CGAL::offset_polygon_2 ( const Polygon_with_holes_2< typename ConicTraits::Rat_kernel, Container > &  pwh,
const typename ConicTraits::Rat_kernel::FT &  r,
const ConicTraits &  traits 
)

Computes the offset of the given polygon with holes pwh by a given radius r.

It does so by offsetting outer boundary of pwh and insetting its holes. The result is represented as a generalized polygon with holes, such that the edges of the polygon correspond to line segments and circular arcs, both are special types of conic arcs, as represented by the traits class.

Precondition
pwh is not unbounded (it has a valid outer boundary).

#include <CGAL/offset_polygon_2.h>

template<class ConicTraits , class Container , class DecompositionStrategy >
Gps_traits_2<ConicTraits>::Polygon_with_holes_2 CGAL::offset_polygon_2 ( const Polygon_2< typename ConicTraits::Rat_kernel, Container > &  P,
const typename ConicTraits::Rat_kernel::FT &  r,
const DecompositionStrategy &  decomp,
const ConicTraits &  traits 
)

Computes the exact representation of the offset of the given polygon P by a radius r, as described above.

If P is not convex, the function decomposes it into convex sub-polygons \( P_1, \ldots, P_k\) and computes the union of sub-offsets (namely \( \bigcup_{i}{(P_i \oplus B_r)}\)). The decomposition is performed using the given decomposition strategy decomp, which must be an instance of a class that models the concept PolygonConvexDecomposition.

Precondition
P is a simple polygon.

#include <CGAL/offset_polygon_2.h>