Polygon

• Class declaration of CGAL_Polygon_2<Traits,Container>.

Algorithms on sequences of 2D points

A number of algorithms on sequences of 2D points is 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	CGAL_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	CGAL_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	CGAL_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	CGAL_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>
CGAL_Bbox_2	CGAL_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	CGAL_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	CGAL_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. The implementation checks if the polygon is locally convex and if there is only one local minimum and one local maximum with respect to the lexicographical ordering determined by Traits::lexicographically_xy_smaller. The complexity of the algorithm is $O(n)$, where $n$ is the number of points in the range [first,last). TRAITS: Traits::lexicographically_xy_smaller, Traits::orientation.
template <class ForwardIterator, class Traits>
bool	CGAL_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. The simplicity test of a polygon is a line-segment intersection test. For the implementation a plane sweep algorithm is used, see also [PS85], p.276. The complexity of the algorithm is $O(n\; log\; n)$ (worst case), where $n$ is the number of points in the range [first,last). TRAITS: Traits::lexicographically_yx_smaller_or_equal, \quad 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>
CGAL_Oriented_side	CGAL_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 CGAL_NEGATIVE_SIDE, or CGAL_POSITIVE_SIDE, or CGAL_ON_ORIENTED_BOUNDARY, depending on where point q is. For the implementation a crossing test algorithm is used with complexity $O(n)$, see [Hai94]. 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>
CGAL_Bounded_side	CGAL_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 CGAL_ON_BOUNDED_SIDE, CGAL_ON_BOUNDARY or CGAL_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>
CGAL_Orientation	CGAL_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, CGAL_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.

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

• Class declaration of CGAL_Polygon_traits_2<R>.