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

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