## ExtremalPolygonTraits_2

| advanced |

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

### Types

ExtremalPolygonTraits_2::FT
| model for FieldNumberType.
ExtremalPolygonTraits_2::Point_2
| model for Kernel::Point_2.
ExtremalPolygonTraits_2::Less_xy_2
| model for Kernel::Less_xy_2.
ExtremalPolygonTraits_2::Orientation_2
| model for Kernel::Orientation_2.
ExtremalPolygonTraits_2::Operation

AdaptableBinaryFunction class op: Point_2 × Point_2 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).

### Operations

int | t.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.)
FT | t.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).)
Operation | t.operation ( const Point_2& p) const
|  | return Operation where p is the fixed root point.
template < class RandomAccessIterator, class OutputIterator >

OutputIterator

t.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 | t.less_xy_2_object ()
Orientation_2 | t.orientation_2_object ()

### Notes

- 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

| advanced |