Reference Manual: Exp

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Requirements for Extremal Polygon Traits Classes

Definition

A class Exp_traits has to provide the following types and operations in order to qualify as a traits class for CGAL_extremal_polygon.

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 vector<Point_2>::iterator and OutputIterator is fixed to vector<int>::reverse_iterator.

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

Requirements for Extremal Polygon Traits Classes

Definition

Types

Operations

Notes

See Also