\( \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.5 - Inscribed Areas
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
ExtremalPolygonTraits_2 Concept Reference

Definition

Advanced

The concept ExtremalPolygonTraits_2 provides the types and operations needed to compute a maximal \( k\)-gon that can be inscribed into a given convex polygon.

Note
ExtremalPolygonTraits_2::Less_xy_2 and ExtremalPolygonTraits_2::Orientation_2 are used for (expensive) precondition checking only. Therefore, they need not to be specified, in case that precondition checking is disabled.
Has Models:

CGAL::Extremal_polygon_area_traits_2<K>

CGAL::Extremal_polygon_perimeter_traits_2<K>

See Also
CGAL::maximum_area_inscribed_k_gon_2()
CGAL::maximum_perimeter_inscribed_k_gon_2()
CGAL::extremal_polygon_2()

Types

typedef unspecified_type FT
 model for FieldNumberType.
 
typedef unspecified_type Point_2
 model for Kernel::Point_2.
 
typedef unspecified_type Less_xy_2
 model for Kernel::Less_xy_2.
 
typedef unspecified_type Orientation_2
 model for Kernel::Orientation_2.
 
typedef unspecified_type Operation
 AdaptableBinaryFunction class op: Point_2 \( \times\) Point_2 \( \rightarrow\) FT. More...
 

Operations

int min_k () const
 returns the minimal \( k\) for which a maximal \( k\)-gon can be computed. More...
 
FT init (const Point_2 &p, const Point_2 &q) const
 returns the value of the objective function for a polygon consisting of the two points p and q. More...
 
Operation operation (const Point_2 &p) const
 return Operation where p is the fixed \( root\) point.
 
template<class RandomAccessIterator , class OutputIterator >
OutputIterator compute_min_k_gon (RandomAccessIterator points_begin, RandomAccessIterator points_end, FT &max_area, OutputIterator o) const
 writes the points of [points_begin, points_end) forming a min_k()-gon rooted at points_begin[0] of maximal value to o and returns the past-the-end iterator for that sequence (== o + min_k()).
 
Less_xy_2 less_xy_2_object ()
 
Orientation_2 orientation_2_object ()
 

Member Typedef Documentation

AdaptableBinaryFunction class op: Point_2 \( \times\) Point_2 \( \rightarrow\) FT.

Together with init this operation recursively defines the objective function to maximize. Let \( p\) and \( q\) be two vertices of a polygon \( P\) such that \( q\) precedes \( p\) in the oriented vertex chain of \( P\) starting with vertex \( root\). Then op(p,q) returns the value by which an arbitrary sub-polygon of \( P\) with vertices from \( [root,\, q]\) increases when \( p\) is added to it. E.g. in the maximum area case this is the area of the triangle \( (root,\, q,\, p)\).

Member Function Documentation

FT ExtremalPolygonTraits_2::init ( const Point_2 p,
const Point_2 q 
) const

returns the value of the objective function for a polygon consisting of the two points p and q.

(e.g. in the maximum area case this is FT( 0).)

int ExtremalPolygonTraits_2::min_k ( ) const

returns the minimal \( k\) for which a maximal \( k\)-gon can be computed.

(e.g. in the maximum area case this is three.)