Requirements for Extremal Polygon Traits Classes

Definition

Types

Exp_traits::Point_2
	class used for representing the input points.
Exp_traits::FT
	class used for doing computations on point coordinates (has to fulfill field-type requirements).
Exp_traits::Operation
	AdaptableBinaryFunction class op: Point_2 $$ × Point_2 $$ 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).

Operations

int	t.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.)
FT	t.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).)
Operation	t.operation ( const Point_2& p) const
		return Operation where p is the fixed $$root point.
template < class RandomAccessIC, class OutputIterator >
OutputIterator	t.compute_min_k_gon ( RandomAccessIC points_begin, RandomAccessIC 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()).
template < class RandomAccessIC >
bool	t.is_convex ( RandomAccessIC points_begin, RandomAccessIC points_end) const
		returns true, iff the points [points_begin, points_end) form a convex chain.

Notes

• Exp_traits::is_convex is only used for precondition checking. Therefore it needs not to be specified, in case that precondition checking is disabled.
• On compilers not supporting member function templates, RandomAccessIC is fixed to std::vector<Point_2>::iterator and OutputIterator is fixed to std::vector<int>::reverse_iterator.

See Also

The classes Kgon_area_traits<R> and Kgon_perimeter_traits<R> (templatized with a CGAL representation class) both fulfill these requirements.