CGAL 5.1.2 - Inscribed Areas
|
This is an advanced concept.
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.
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.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 () |
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)\).
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.)