CGAL 6.1 - 2D Minkowski Sums

Loading...
Searching...
No Matches
Classes | Functions
CGAL Namespace Reference

## Classes
class | Greene_convex_decomposition_2
| 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 | Hertel_Mehlhorn_convex_decomposition_2
| 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 | Optimal_convex_decomposition_2
| 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 | Polygon_nop_decomposition_2
| 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 | Polygon_triangulation_decomposition_2
| 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 | Polygon_vertical_decomposition_2
| 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 | Small_side_angle_bisector_decomposition_2
| 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 | 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 | 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 | 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 | 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 > | 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 > | 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 > | 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 > | 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 > | 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 > | 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 | 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 | 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 | 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 | 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.