CGAL 5.1.2 - 2D Minkowski Sums
|
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.
CGAL::minkowski_sum_2()
CGAL::minkowski_sum_by_decomposition_2()
CGAL::minkowski_sum_by_full_convolution_2()
CGAL::minkowski_sum_by_reduced_convolution_2()
CGAL::approximated_offset_2()
CGAL::approximated_inset_2()
CGAL::offset_polygon_2()
CGAL::inset_polygon_2()
CGAL::Small_side_angle_bisector_decomposition_2<Kernel,Container>
CGAL::Optimal_convex_decomposition_2<Kernel,Container>
CGAL::Hertel_Mehlhorn_convex_decomposition_2<Kernel,Container>
CGAL::Greene_convex_decomposition_2<Kernel,Container>
CGAL::Polygon_vertical_decomposition_2<Kernel,Container>
CGAL::Polygon_triangulation_decomposition_2<Kernel,Container>
CGAL::Polygon_nop_decomposition_2<Kernel,Container>
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 [6]. 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 [6]. 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... | |
OutputIterator CGAL::approximated_inset_2 | ( | const Polygon_2< Kernel, Container > & | pgn, |
const typename Kernel::FT & | r, | ||
const double & | eps, | ||
OutputIterator | oi | ||
) |
#include <CGAL/approximated_offset_2.h>
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
.
P
is a simple polygon. 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 | ||
) |
#include <CGAL/approximated_offset_2.h>
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.
P
is a simple polygon. 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 | ||
) |
#include <CGAL/approximated_offset_2.h>
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.
pwh
is not unbounded (it has a valid outer boundary). 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 | ||
) |
#include <CGAL/approximated_offset_2.h>
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
.
P
is a simple polygon. 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 | ||
) |
#include <CGAL/offset_polygon_2.h>
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
.
P
is a simple polygon. Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_2 | ( | const PolygonType1< Kernel, Container > & | P, |
const PolygonType2< Kernel, Container > & | Q | ||
) |
#include <CGAL/minkowski_sum_2.h>
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.
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 >() |
||
) |
#include <CGAL/minkowski_sum_2.h>
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)}\)).
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 >() |
||
) |
#include <CGAL/minkowski_sum_2.h>
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
.
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 >() |
||
) |
#include <CGAL/minkowski_sum_2.h>
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.
PolygonNoHolesConvexDecomposition_2_ | a model of the concept PolygonConvexDecomposition_2 . |
PolygonWithHolesConvexDecomposition_2_ | a model of the concept PolygonWithHolesConvexDecomposition_2 . |
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 | ||
) |
#include <CGAL/minkowski_sum_2.h>
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:
Polygon_with_holes_2<Kernel, Container> CGAL::minkowski_sum_by_reduced_convolution_2 | ( | const PolygonType1< Kernel, Container > & | P, |
const PolygonType2< Kernel, Container > & | Q | ||
) |
#include <CGAL/minkowski_sum_2.h>
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:
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 | ||
) |
#include <CGAL/offset_polygon_2.h>
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.
P
is a simple polygon. 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 | ||
) |
#include <CGAL/offset_polygon_2.h>
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.
pwh
is not unbounded (it has a valid outer boundary). 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 | ||
) |
#include <CGAL/offset_polygon_2.h>
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
.
P
is a simple polygon.