#include <CGAL/Polygon_2.h>

Definition

The class Polygon_2 implements polygons.

The Polygon_2 is parameterized by a traits class and a container class. The latter can be any class that fulfills the requirements for an STL container. It defaults to the std::vector class.

Implementation

The methods is_simple(), is_convex(), orientation(), oriented_side(), bounded_side(), bbox(), area(), left_vertex(), right_vertex(), top_vertex() and bottom_vertex() are all implemented using the algorithms on sequences of 2D points. See the corresponding global functions for information about which algorithms were used and what complexity they have.

Examples:: Polygon/Example.cpp, and Polygon/Polygon.cpp.

Global Operators
template<class Traits_P , class Container1_P , class Container2_P >
bool	operator== (const Polygon_2< Traits_P, Container1_P > &p1, const Polygon_2< Traits_P, Container2_P > &p2)
	Test for equality: two polygons are equal iff there exists a cyclic permutation of the vertices of `p2` such that they are equal to the vertices of `p1`. More...

template<class Traits_P , class Container1_P , class Container2_P >
bool	operator!= (const Polygon_2< Traits_P, Container1_P > &p1, const Polygon_2< Traits_P, Container2_P > &p2)
	Test for inequality.

template<class Transformation , class Traits_P , class Container_P >
Polygon_2< Traits_P, Container_P >	transform (const Transformation &t, const Polygon_2< Traits_P, Container_P > &p)
	Returns the image of the polygon `p` under the transformation `t`.

I/O
The information output in the `std::iostream` is the number of points followed by the output of the coordinates of the vertices.
template<class Traits_P , class Container_P >
std::istream &	operator>> (std::istream &is, Polygon_2< Traits_P, Container_P > &p)
	Inserts the polygon `p` into the stream `os`. More...

template<class Traits_P , class Container_P >
std::ostream &	operator<< (std::ostream &os, const Polygon_2< Traits_P, Container_P > &p)
	Reads a polygon from stream `is` and assigns it to `p`. More...

Types
typedef Container_P	Container
	The container type.

typedef Traits_P::FT	FT
	The number type of the coordinates of the points of the polygon.

typedef Traits_P::Point_2	Point_2
	The point type of the polygon.

typedef Traits_P::Segment_2	Segment_2
	The type of a segment between two points of the polygon.

Iterators
The following types denote iterators that allow to traverse the vertices and edges of a polygon. Since a polygon can be viewed as a circular as well as a linear data structure both circulators and iterators are defined. Note At least conceptually, the circulators and iterators are non-mutable. The enforcement depends on preprocessor flags. The iterator category is in all cases bidirectional, except for Vertex_iterator, which has the same iterator category as `Container::iterator`. In fact all of them should have the same iterator category as `Container::iterator`. However, due to compiler problems this is currently not possible.
typedef Container::iterator	Vertex_iterator

typedef unspecified_type	Vertex_circulator

typedef unspecified_type	Edge_const_iterator

typedef unspecified_type	Edge_const_circulator

Creation
	Polygon_2 (const Traits &p_traits=Traits())
	Creates an empty polygon.

	Polygon_2 (const Polygon_2< Traits_P, Container_P > &polygon)
	Copy constructor.

template<class InputIterator >
	Polygon_2 (InputIterator first, InputIterator last, Traits p_traits=Traits())
	Introduces a polygon with vertices from the sequence defined by the range [first,last). More...

Modifiers
void	set (Vertex_iterator i, const Point_2 &q)
	Acts as `*i = q`, except that that would be illegal because the iterator is not mutable. More...

void	set (Polygon_circulator< Container >const &i, const Point_2 &q)

Vertex_iterator	insert (Vertex_iterator i, const Point_2 &q)
	Inserts the vertex `q` before `i`. More...

Vertex_iterator	insert (Vertex_circulator i, const Point_2 &q)

Access Functions
The following methods of the class Polygon_2 return circulators and iterators that allow to traverse the vertices and edges.
Vertex_const_iterator	vertices_begin () const
	Returns a constant iterator that allows to traverse the vertices of the polygon. More...

Vertex_const_iterator	vertices_end () const
	Returns the corresponding past-the-end iterator.

Vertex_const_circulator	vertices_circulator () const
	Returns a mutable circulator that allows to traverse the vertices of the polygon. More...

Edge_const_iterator	edges_begin () const
	Returns a non-mutable iterator that allows to traverse the edges of the polygon. More...

Edge_const_iterator	edges_end () const
	Returns the corresponding past-the-end iterator.

Edge_const_circulator	edges_circulator () const
	Returns a non-mutable circulator that allows to traverse the edges of the polygon. More...

Predicates
bool	is_simple () const
	Returns whether this is a simple polygon.

bool	is_convex () const
	Returns whether this is convex.

Orientation	orientation () const
	Returns the orientation. More...

Oriented_side	oriented_side (const Point_2 &value) const
	Returns `POSITIVE_SIDE`, or `NEGATIVE_SIDE`, or `ON_ORIENTED_BOUNDARY`, depending on where point `q` is. More...

Bounded_side	bounded_side (const Point_2 &value) const
	Returns the symbolic constant `ON_BOUNDED_SIDE`, `ON_BOUNDARY` or `ON_UNBOUNDED_SIDE`, depending on where point `q` is. More...

Bbox_2	bbox () const
	Returns the smallest bounding box containing this polygon.

FT	area () const
	Returns the signed area of the polygon. More...

Vertex_const_iterator	left_vertex () const
	Returns the leftmost vertex of the polygon with the smallest `x`-coordinate. More...

Vertex_const_iterator	right_vertex () const
	Returns the rightmost vertex of the polygon with the largest `x`-coordinate. More...

Vertex_const_iterator	top_vertex () const
	Returns topmost vertex of the polygon with the largest `y`-coordinate. More...

Vertex_const_iterator	bottom_vertex () const
	Returns the bottommost vertex of the polygon with the smallest `y`-coordinate. More...

For convenience we provide the following Boolean functions:
bool	is_counterclockwise_oriented () const

bool	is_clockwise_oriented () const

bool	is_collinear_oriented () const

bool	has_on_positive_side (const Point_2 &q) const

bool	has_on_negative_side (const Point_2 &q) const

bool	has_on_boundary (const Point_2 &q) const

bool	has_on_bounded_side (const Point_2 &q) const

bool	has_on_unbounded_side (const Point_2 &q) const

Random Access Methods
const Point_2 &	vertex (std::size_t i) const
	Returns a (const) reference to the `i`-th vertex.

const Point_2 &	operator[] (std::size_t i) const
	Returns a (const) reference to the `i`-th vertex.

Segment_2	edge (std::size_t i) const
	Returns the `i`-th edge.

Miscellaneous
std::size_t	size () const
	Returns the number of vertices of the polygon.

bool	is_empty () const
	Returns `size() == 0`.

const Container_P &	container () const
	Returns a const reference to the sequence of vertices of the polygon.

Constructor & Destructor Documentation

template<class _Traits , class _Container >

template<class InputIterator >

CGAL::Polygon_2< _Traits, _Container >::Polygon_2	(	InputIterator	first,
		InputIterator	last,
		Traits	p_traits = `Traits()`
	)

Introduces a polygon with vertices from the sequence defined by the range [first,last).

The value type of InputIterator must be Point_2.

Member Function Documentation

template<class _Traits , class _Container >

FT CGAL::Polygon_2< _Traits, _Container >::area ( ) const

Returns the signed area of the polygon.

This means that the area is positive for counter clockwise polygons and negative for clockwise polygons.

template<class _Traits , class _Container >

Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::bottom_vertex ( ) const

Returns the bottommost vertex of the polygon with the smallest y-coordinate.

template<class _Traits , class _Container >

Bounded_side CGAL::Polygon_2< _Traits, _Container >::bounded_side ( const Point_2 & value ) const

Returns the symbolic constant ON_BOUNDED_SIDE, ON_BOUNDARY or ON_UNBOUNDED_SIDE, depending on where point q is.

Precondition: p.is_simple().

template<class _Traits , class _Container >

Edge_const_iterator CGAL::Polygon_2< _Traits, _Container >::edges_begin ( ) const

Returns a non-mutable iterator that allows to traverse the edges of the polygon.

template<class _Traits , class _Container >

Edge_const_circulator CGAL::Polygon_2< _Traits, _Container >::edges_circulator ( ) const

Returns a non-mutable circulator that allows to traverse the edges of the polygon.

template<class _Traits , class _Container >

Vertex_iterator CGAL::Polygon_2< _Traits, _Container >::insert	(	Vertex_iterator	i,
		const Point_2 &	q
	)

Inserts the vertex q before i.

The return value points to the inserted vertex.

template<class _Traits , class _Container >

Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::left_vertex ( ) const

Returns the leftmost vertex of the polygon with the smallest x-coordinate.

template<class Traits_P , class Container_P >

std::ostream & operator<<	(	std::ostream &	os,
		const Polygon_2< Traits_P, Container_P > &	p
	)

Reads a polygon from stream is and assigns it to p.

Precondition: The extract operator must be defined for Point_2.

template<class Traits_P , class Container1_P , class Container2_P >

bool operator==	(	const Polygon_2< Traits_P, Container1_P > &	p1,
		const Polygon_2< Traits_P, Container2_P > &	p2
	)

Test for equality: two polygons are equal iff there exists a cyclic permutation of the vertices of p2 such that they are equal to the vertices of p1.

Note that the template argument Container of p1 and p2 may be different.

template<class Traits_P , class Container_P >

std::istream & operator>>	(	std::istream &	is,
		Polygon_2< Traits_P, Container_P > &	p
	)

Inserts the polygon p into the stream os.

Precondition: The insert operator must be defined for Point_2.

template<class _Traits , class _Container >

Orientation CGAL::Polygon_2< _Traits, _Container >::orientation ( ) const

Returns the orientation.

If the number of vertices p.size() < 3 then COLLINEAR is returned.

Precondition: p.is_simple().

template<class _Traits , class _Container >

Oriented_side CGAL::Polygon_2< _Traits, _Container >::oriented_side ( const Point_2 & value ) const

Returns POSITIVE_SIDE, or NEGATIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is.

Precondition: p.is_simple().

template<class _Traits , class _Container >

Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::right_vertex ( ) const

Returns the rightmost vertex of the polygon with the largest x-coordinate.

template<class _Traits , class _Container >

void CGAL::Polygon_2< _Traits, _Container >::set	(	Vertex_iterator	i,
		const Point_2 &	q
	)

Acts as *i = q, except that that would be illegal because the iterator is not mutable.

template<class _Traits , class _Container >

Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::top_vertex ( ) const

Returns topmost vertex of the polygon with the largest y-coordinate.

template<class _Traits , class _Container >

Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::vertices_begin ( ) const

Returns a constant iterator that allows to traverse the vertices of the polygon.

template<class _Traits , class _Container >

Vertex_const_circulator CGAL::Polygon_2< _Traits, _Container >::vertices_circulator ( ) const

Returns a mutable circulator that allows to traverse the vertices of the polygon.

Definition

Global Operators

I/O

Types

Iterators

Creation

Modifiers

Access Functions

Predicates

Random Access Methods

Miscellaneous

Constructor & Destructor Documentation

Member Function Documentation