CGAL 4.12 - Inscribed Areas
|
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.)