#include <CGAL/Polygon_2.h>

Definition

template<class Traits_P, class Container_P = std::vector<typename Traits_P::Point_2>>
class CGAL::Polygon_2< Traits_P, Container_P >

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_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
	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_P &	container () const
	Returns a const reference to the sequence of vertices of the polygon.

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

Container_P::iterator	begin ()
	Returns an iterator to the first vertex of the polygon.

Container_P::iterator	end ()
	Returns an iterator to the element after the last vertex of the polygon.

const Container_P::const_iterator	begin () const
	Returns a const iterator to the first vertex of the polygon.

const Container_P::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_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`.

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)
	Reads a polygon from stream `is` and assigns it to `p`.

template<class Traits_P , class Container_P >
std::ostream &	operator<< (std::ostream &os, const Polygon_2< Traits_P, Container_P > &p)
	Inserts the polygon `p` into the stream `os`.

Constructor & Destructor Documentation

◆ Polygon_2()

template<class Traits_P , class Container_P = std::vector<typename Traits_P::Point_2>>

template<class InputIterator >

CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

FT CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

Bounded_side CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

Vertex_iterator CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

template<class InputIterator >

void CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

Vertex_iterator CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

template<class InputIterator >

void CGAL::Polygon_2< Traits_P, Container_P >::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_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.

◆ orientation()

template<class Traits_P , class Container_P = std::vector<typename Traits_P::Point_2>>

Orientation CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

Oriented_side CGAL::Polygon_2< Traits_P, Container_P >::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_P , class Container_P = std::vector<typename Traits_P::Point_2>>

void CGAL::Polygon_2< Traits_P, Container_P >::reverse_orientation ( )

Reverses the orientation of the polygon.

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

Friends And Related Function Documentation

◆ operator<<()

template<class Traits_P , class Container_P >

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

Precondition: The insert operator must be defined for Point_2.

◆ operator>>()

template<class Traits_P , class Container_P >

std::istream & operator>>	(	std::istream &	is,
		Polygon_2< Traits_P, Container_P > &	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 Function Documentation

◆ operator<<()

◆ operator>>()