#include <CGAL/Polygon_2.h>

Definition

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>
class CGAL::Polygon_2< Traits_, Container_ >

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, and has a function resize() that takes an std::size_t as argument. 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, Polygon/Polygon.cpp, Polygon/draw_polygon.cpp, Polygon/draw_polygon_with_holes.cpp, Polygon/multipolygon.cpp, and Polygon/ranges.cpp.

Types
typedef Container_	Container
	The container type.
typedef Traits_::FT	FT
	The number type of the coordinates of the points of the polygon.
typedef Traits_::Point_2	Point_2
	The point type of the polygon.
typedef Traits_::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
	vertex iterator type
typedef Container	Vertices
	a range type to iterate over the vertices
typedef unspecified_type	Vertex_circulator
	vertex circulator type
typedef unspecified_type	Edge_const_iterator
	edge iterator type
typedef unspecified_type	Edges
	a range type to iterate over the vertices
typedef unspecified_type	Edge_const_circulator
	edge circular type

Creation
	Polygon_2 ()=default
	Creates an empty polygon.
	Polygon_2 (const Traits &p_traits)
	Creates an empty polygon.
template<class InputIterator>
	Polygon_2 (InputIterator first, InputIterator last, Traits p_traits=Traits())
	Creates a polygon with vertices from the sequence defined by the range [first,last).

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.
Vertex_iterator	insert (Vertex_iterator i, const Point_2 &q)
	Inserts the vertex q before i.
Vertex_iterator	insert (Vertex_circulator i, const Point_2 &q)
	Inserts the vertex q before i.
template<class InputIterator>
void	insert (Vertex_iterator i, InputIterator first, InputIterator last)
	Inserts the vertices in the range [first, last) before i.
template<class InputIterator>
void	insert (Vertex_circulator i, InputIterator first, InputIterator last)
	Inserts the vertices in the range [first, last) before i.
void	push_back (const Point_2 &x)
	Has the same semantics as p.insert(p.vertices_end(), q).
Vertex_iterator	erase (Vertex_iterator i)
	Erases the vertex pointed to by i.
Vertex_circulator	erase (Vertex_circulator i)
	Erases the vertex pointed to by i.
Vertex_iterator	erase (Vertex_iterator first, Vertex_iterator last)
	Erases the vertices in the range [first, last).
void	clear ()
	Erases the vertices in the range [first, last).
void	reverse_orientation ()
	Reverses the orientation of the polygon.

Access Functions
The following methods of the class Polygon_2 return circulators and iterators that allow to traverse the vertices and edges.
Vertex_iterator	vertices_begin () const
	Returns a constant iterator that allows to traverse the vertices of the polygon.
Vertex_iterator	vertices_end () const
	Returns the corresponding past-the-end iterator.
const Vertices &	vertices () const
	returns the range of vertices.
Vertex_circulator	vertices_circulator () const
	Returns a constant circulator that allows to traverse the vertices of the polygon.
Edge_const_iterator	edges_begin () const
	Returns a non-mutable iterator that allows to traverse the edges of the polygon.
Edge_const_iterator	edges_end () const
	Returns the corresponding past-the-end iterator.
Edges	edges () const
	returns the range of edges.
Edge_const_circulator	edges_circulator () const
	Returns a non-mutable circulator that allows to traverse the edges of the polygon.

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.
Oriented_side	oriented_side (const Point_2 &value) const
	Returns ON_POSITIVE_SIDE, or ON_NEGATIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is.
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.
Bbox_2	bbox () const
	Returns the smallest bounding box containing this polygon.
FT	area () const
	Returns the signed area of the polygon.
Vertex_const_iterator	left_vertex () const
	Returns the leftmost vertex of the polygon with the smallest x-coordinate.
Vertex_const_iterator	right_vertex () const
	Returns the rightmost vertex of the polygon with the largest x-coordinate.
Vertex_const_iterator	top_vertex () const
	Returns the topmost vertex of the polygon with the largest y-coordinate.
Vertex_const_iterator	bottom_vertex () const
	Returns the bottommost vertex of the polygon with the smallest y-coordinate.

Convenience Orientation Functions
For convenience we provide the following Boolean functions:
bool	is_counterclockwise_oriented () const
	returns orientation() == COUNTERCLOCKWISE
bool	is_clockwise_oriented () const
	returns orientation() == CLOCKWISE
bool	is_collinear_oriented () const
	returns orientation() == COLLINEAR
bool	has_on_positive_side (const Point_2 &q) const
	returns oriented_side(q) == ON_POSITIVE_SIDE
bool	has_on_negative_side (const Point_2 &q) const
	returns oriented_side(q) == ON_NEGATIVE_SIDE
bool	has_on_boundary (const Point_2 &q) const
	returns bounded_side(q) == ON_BOUNDARY
bool	has_on_bounded_side (const Point_2 &q) const
	returns bounded_side(q) == ON_BOUNDED_SIDE
bool	has_on_unbounded_side (const Point_2 &q) const
	returns bounded_side(q) == ON_UNBOUNDED_SIDE

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.
Point_2 &	vertex (std::size_t i)
	Returns a reference to the i-th vertex.
Point_2 &	operator[] (std::size_t i)
	Returns a 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_ &	container () const
	Returns a const reference to the sequence of vertices of the polygon.
Container_ &	container ()
	Returns a reference to the sequence of vertices of the polygon.
Container_::iterator	begin ()
	Returns an iterator to the first vertex of the polygon.
Container_::iterator	end ()
	Returns an iterator to the element after the last vertex of the polygon.
const Container_::const_iterator	begin () const
	Returns a const iterator to the first vertex of the polygon.
const Container_::const_iterator	end () const
	Returns a const iterator to the element after the last vertex of the polygon.
void	resize (std::size_t s)
	Resizes the container. Calls container().resize(s).
void	reserve (std::size_t s)
	Calls container().reserve(s) if this is available for Container.

Global Operators
template<class Traits_, class Container1_P, class Container2_P>
bool	operator== (const Polygon_2< Traits_, Container1_P > &p1, const Polygon_2< Traits_, 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.
template<class Traits_, class Container1_P, class Container2_P>
bool	operator!= (const Polygon_2< Traits_, Container1_P > &p1, const Polygon_2< Traits_, Container2_P > &p2)
	Test for inequality.
template<class Transformation, class Traits_, class Container_>
Polygon_2< Traits_, Container_ >	transform (const Transformation &t, const Polygon_2< Traits_, Container_ > &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_, class Container_>
std::istream &	operator>> (std::istream &is, Polygon_2< Traits_, Container_ > &p)
	Reads a polygon from stream is and assigns it to p.
template<class Traits_, class Container_>
std::ostream &	operator<< (std::ostream &os, const Polygon_2< Traits_, Container_ > &p)
	Inserts the polygon p into the stream os.

Constructor & Destructor Documentation

◆ Polygon_2()

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

template<class InputIterator>

CGAL::Polygon_2< Traits_, Container_ >::Polygon_2	(	InputIterator	first,
		InputIterator	last,
		Traits	p_traits = Traits() )

Creates 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

◆ area()

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

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.

◆ bounded_side()

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

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

◆ insert() [1/4]

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

Vertex_iterator CGAL::Polygon_2< Traits_, Container_ >::insert	(	Vertex_circulator	i,
		const Point_2 &	q )

Inserts the vertex q before i.

The return value points to the inserted vertex.

◆ insert() [2/4]

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

template<class InputIterator>

void CGAL::Polygon_2< Traits_, Container_ >::insert	(	Vertex_circulator	i,
		InputIterator	first,
		InputIterator	last )

Inserts the vertices in the range [first, last) before i.

The value type of points in the range [first,last) must be Point_2.

◆ insert() [3/4]

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

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.

◆ insert() [4/4]

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

template<class InputIterator>

void CGAL::Polygon_2< Traits_, Container_ >::insert	(	Vertex_iterator	i,
		InputIterator	first,
		InputIterator	last )

Inserts the vertices in the range [first, last) before i.

The value type of points in the range [first,last) must be Point_2.

◆ operator==()

template<class Traits_, class Container1_P, class Container2_P>

bool operator==	(	const Polygon_2< Traits_, Container1_P > &	p1,
		const Polygon_2< Traits_, 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.

◆ orientation()

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

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

◆ oriented_side()

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

Oriented_side CGAL::Polygon_2< Traits_, Container_ >::oriented_side ( const Point_2 & value ) const

Returns ON_POSITIVE_SIDE, or ON_NEGATIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is.

Precondition: p.is_simple().

◆ reverse_orientation()

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>

void CGAL::Polygon_2< Traits_, Container_ >::reverse_orientation ( )

Reverses the orientation of the polygon.

The vertex pointed to by p.vertices_begin() remains the same.

◆ operator<<()

template<class Traits_, class Container_>

std::ostream & operator<<	(	std::ostream &	os,
		const Polygon_2< Traits_, Container_ > &	p )

Inserts the polygon p into the stream os.

Precondition: The insert operator must be defined for Point_2.

◆ operator>>()

template<class Traits_, class Container_>

std::istream & operator>>	(	std::istream &	is,
		Polygon_2< Traits_, Container_ > &	p )

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

Precondition: The extract operator must be defined for Point_2.

Definition

Types

Iterators

Creation

Modifiers

Access Functions

Predicates

Convenience Orientation Functions

Random Access Methods

Miscellaneous

Global Operators

I/O

Constructor & Destructor Documentation

◆ Polygon_2()

Member Function Documentation

◆ area()

◆ bounded_side()

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ operator==()

◆ orientation()

◆ oriented_side()

◆ reverse_orientation()

Friends And Related Symbol Documentation

◆ operator<<()

◆ operator>>()