Polygon

• Class declaration of Polygon_2<Traits,Container>.

Algorithms on sequences of 2D points

A number of algorithms on sequences of 2D points are supplied as global functions. In all algorithms the points in the range [first,last) are interpreted as the vertices of a polygon. The vertices in this range should have value type Traits::Point_2. Most functions take a traits class as their last argument. This is just a technical matter: the template argument Traits must appear in the arguments of the function. Modern compilers should be able to optimize this traits argument away. In all cases a default version of the function exists without the Traits argument. These default versions use the predefined polygon traits class from section .

template <class ForwardIterator, class Traits>
ForwardIterator	left_vertex_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns the leftmost point from the range [first,last) with the smallest y-coordinate. TRAITS: uses Traits::Less_xy.
template <class ForwardIterator, class Traits>
ForwardIterator	right_vertex_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns the rightmost point in the range [first,last) with the largest y-coordinate. TRAITS: uses Traits::Less_xy.
template <class ForwardIterator, class Traits>
ForwardIterator	top_vertex_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns the topmost point from the range [first,last) with the largest x-coordinate. TRAITS: uses Traits::Less_yx.
template <class ForwardIterator, class Traits>
ForwardIterator	bottom_vertex_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns the bottommost point from the range [first,last) with the smallest x-coordinate. TRAITS: uses Traits::Less_yx.
template <class InputIterator>
Bbox_2	bbox_2 ( InputIterator first, InputIterator last)
		Returns the smallest bounding box of the points in the range [first,last). Precondition: The range [first,last) is not empty.
template <class ForwardIterator, class Numbertype, class Traits>
void	area_2 ( ForwardIterator first, ForwardIterator last, Numbertype& result, Traits traits)
		Computes the signed area of the polygon formed by the points in the range [first,last). TRAITS: uses Traits::determinant_2.
template <class ForwardIterator, class Traits>
bool	is_convex_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns true if the polygon formed by the points in the range [first,last) is convex. TRAITS: Traits::lexicographically_xy_smaller, Traits::orientation.
template <class ForwardIterator, class Traits>
bool	is_simple_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns true if the polygon formed by the points in the range [first,last) is simple. TRAITS: Traits::lexicographically_yx_smaller_or_equal, Traits::do_intersect, Traits::have_equal_direction. Traits::compare_x, Traits::compare_y, Traits::cross_product_2, Traits::is_negative,
template <class ForwardIterator, class Point, class Traits>
Oriented_side	oriented_side_2 ( ForwardIterator first, ForwardIterator last, Traits::Point_2 point, Traits traits)
		This determines the location of the point q with respect to the polygon formed by the points in the range [first,last). It returns NEGATIVE_SIDE, or POSITIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is. Precondition: The points in the range [first,last) form the vertices of a simple polygon. TRAITS: uses Traits::Less_xy, Traits::compare_x, Traits::compare_y, Traits::determinant_2, Traits::orientation and Traits::sign.
template <class ForwardIterator, class Point, class Traits>
Bounded_side	bounded_side_2 ( ForwardIterator first, ForwardIterator last, Traits::Point_2 point, Traits traits)
		Determines the location of the point q with respect to the polygon formed by the points in the range [first,last). It returns either ON_BOUNDED_SIDE, ON_BOUNDARY or ON_UNBOUNDED_SIDE, depending on where point q is. Precondition: The points in the range [first,last) form the vertices of a simple polygon. TRAITS: uses Traits::compare_x, Traits::compare_y, Traits::determinant_2 and Traits::determinant_2.
template <class ForwardIterator, class Traits>
Orientation	orientation_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
		Returns the orientation of the polygon formed by the points in the range [first,last). If the number of points is smaller than three, COLLINEAR is returned. Precondition: The points in the range [first,last) form the vertices of a simple polygon. TRAITS: uses Traits::Less_xy and Traits::orientation.

Implementation

Polygon Traits class requirements

The polygon algorithms in section are parameterized with a traits class Traits that defines the basic types and predicates that the algorithms use. This section describes the minimal requirements for the traits class. N.B. Currently the list of requirements contains several redundant predicates that can be easily expressed in others. For example, the lexicographical comparison functions can be expressed in the functions compare_x and compare_y). These predicates will probably be removed from the traits class.

• Class declaration of Polygon_traits.

• Class declaration of Polygon_traits_2<R>.