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.