CGAL 6.1 - Inscribed Areas

Loading...
Searching...
No Matches
List of all members
ExtremalPolygonTraits_2 Concept Reference
Reference Manual » Concepts

## Definition

This is an advanced concept.

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::LessXY_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`.

## Operations
int | min_k () const
| returns the minimal \( k\) for which a maximal \( k\)-gon can be computed.
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`.
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

## ◆ Operation

typedef unspecified_type ExtremalPolygonTraits_2::Operation

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

## ◆ init()

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

## ◆ min_k()

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