\( \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.7 - 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-15b
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 >
 
class  CGAL::Optimal_convex_decomposition_2< Kernel, Container >
 
class  CGAL::Polygon_triangulation_decomposition_2< Kernel, Container >
 
class  CGAL::Polygon_vertical_decomposition_2< Kernel, Container >
 
class  CGAL::Small_side_angle_bisector_decomposition_2< Kernel, Container >
 

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 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<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 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.

If the input polygons P and Q are not convex, the function decomposes them into convex sub-polygons \( P_1, \ldots, P_k\) and \( Q_1, \ldots, Q_{\ell}\) and 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, which must be an instance of a class template that models the concept PolygonConvexDecomposition_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 [2] 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>