CGAL 6.1 - 2D Minkowski Sums

Loading...
Searching...
No Matches
Modules | Classes | Functions
Reference Manual

##

Ron Wein, Alon Baram, Eyal Flato, Efi Fogel, Michael Hemmer, and 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, 2D and 3D Fast Intersection and Distance Computation, 2D Triangulations
BibTeX: cgal:w-rms2-25b
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

- `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()`

## Concepts

- `PolygonConvexDecomposition_2`
- `PolygonWithHolesConvexDecomposition_2`

## Classes

- `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::Hertel_Mehlhorn_convex_decomposition_2< Kernel, Container >
| The `Hertel_Mehlhorn_convex_decomposition_2` class implements the approximation algorithm of Hertel and Mehlhorn for decomposing a polygon into convex sub-polygons [8]. 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 decomposition 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`.
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.
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`.
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.
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).
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.
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.
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.
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.
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.
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 \}\).
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.
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`.
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.

## Function Documentation

## ◆ approximated_inset_2()

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

`#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<Kernel>::Polygon_2`.

Precondition
  `P` is a simple polygon.

## ◆ approximated_offset_2() [1/3]

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

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

Precondition
  `P` is a simple polygon.

Examples
  Minkowski_sum_2/approx_offset.cpp.

## ◆ approximated_offset_2() [2/3]

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

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

Precondition
  `P` is a simple polygon.

## ◆ approximated_offset_2() [3/3]

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

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

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

## ◆ inset_polygon_2()

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

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

Precondition
  `P` is a simple polygon.

## ◆ minkowski_sum_2() [1/3]

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

`#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:

- `Polygon_2`
- `Polygon_with_holes_2`

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()`

Examples
  Minkowski_sum_2/sum_by_decomposition.cpp, Minkowski_sum_2/sum_triangle_square.cpp, and Minkowski_sum_2/sum_with_holes.cpp.

## ◆ minkowski_sum_2() [2/3]

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 >()`
| ) |  |

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

## ◆ minkowski_sum_2() [3/3]

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 >()`
| ) |  |

`#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)}\)).

## ◆ minkowski_sum_by_decomposition_2()

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 >()`
| ) |  |

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

Template Parameters

  PolygonNoHolesConvexDecomposition_2_ | a model of the concept `PolygonConvexDecomposition_2`.
  PolygonWithHolesConvexDecomposition_2_ | a model of the concept `PolygonWithHolesConvexDecomposition_2`.

## ◆ minkowski_sum_by_full_convolution_2()

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

`#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_2`
- `Polygon_with_holes_2`

## ◆ minkowski_sum_by_reduced_convolution_2()

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

`#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:

- `Polygon_2`
- `Polygon_with_holes_2`

## ◆ offset_polygon_2() [1/3]

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

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

Precondition
  `P` is a simple polygon.

Examples
  Minkowski_sum_2/exact_offset.cpp.

## ◆ offset_polygon_2() [2/3]

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

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

Precondition
  `P` is a simple polygon.

## ◆ offset_polygon_2() [3/3]

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

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

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