ExtremalPolygonTraits_2 Class Reference

#include <Concepts/ExtremalPolygonTraits_2.h>

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

FT

typedef unspecified_type ExtremalPolygonTraits_2::FT

model for FieldNumberType.

Less_xy_2

typedef unspecified_type ExtremalPolygonTraits_2::Less_xy_2

model for Kernel::Less_xy_2.

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

Orientation_2

typedef unspecified_type ExtremalPolygonTraits_2::Orientation_2

model for Kernel::Orientation_2.

Point_2

typedef unspecified_type ExtremalPolygonTraits_2::Point_2

model for Kernel::Point_2.

Member Function Documentation

compute_min_k_gon()

template<class RandomAccessIterator , class OutputIterator >

OutputIterator ExtremalPolygonTraits_2::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()).

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

less_xy_2_object()

Less_xy_2 ExtremalPolygonTraits_2::less_xy_2_object

(

)

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

operation()

Operation ExtremalPolygonTraits_2::operation

(

const Point_2 &

p

)

const

return Operation where p is the fixed \( root\) point.

orientation_2_object()

Orientation_2 ExtremalPolygonTraits_2::orientation_2_object

(

)