ExtremalPolygonTraits_2 Concept Reference

Definition

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

Member Typedef Documentation

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

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

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