CGAL 4.7 - Inscribed Areas
ExtremalPolygonTraits_2 Concept Reference

## Definition

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>

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