#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/draw_polygon.cpp, Polygon/draw_polygon_with_holes.cpp, 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)
	Reads a polygon from stream `is` and assigns it to `p`. More...

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`. 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
	vertex iterator type

typedef unspecified_type	Vertex_circulator
	vertex circulator type

typedef unspecified_type	Edge_const_iterator
	edge circulator type

typedef unspecified_type	Edge_const_circulator
	edge circular type

Creation
	Polygon_2 ()
	Creates an empty polygon.

	Polygon_2 (const Traits &p_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())
	Creates 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...

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)
	Inserts the vertex `q` before `i`. More...

template<class InputIterator >
void	insert (Vertex_iterator i, InputIterator first, InputIterator last)
	Inserts the vertices in the range `[first, last)` before `i`. More...

template<class InputIterator >
void	insert (Vertex_circulator i, InputIterator first, InputIterator last)
	Inserts the vertices in the range `[first, last)` before `i`. More...

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

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 `ON_POSITIVE_SIDE`, or `ON_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...

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

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.

◆ bottom_vertex()

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

Vertex_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::bottom_vertex ( ) const

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

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

◆ edges_begin()

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

Edge_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::edges_begin ( ) const

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

◆ edges_circulator()

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

Edge_const_circulator CGAL::Polygon_2< Traits_P, Container_P >::edges_circulator ( ) const

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

◆ 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_iterator	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>>

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() [3/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.

◆ 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_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.

◆ left_vertex()

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

Vertex_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::left_vertex ( ) const

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

◆ operator<<()

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.

Precondition: The insert operator must be defined for 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.

◆ operator>>()

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.

Precondition: The extract operator must be defined for Point_2.

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

◆ right_vertex()

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

Vertex_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::right_vertex ( ) const

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

◆ set()

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

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

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

◆ top_vertex()

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

Vertex_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::top_vertex ( ) const

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

◆ vertices_begin()

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

Vertex_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::vertices_begin ( ) const

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

◆ vertices_circulator()

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

Vertex_const_circulator CGAL::Polygon_2< Traits_P, Container_P >::vertices_circulator ( ) const

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

Definition

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

Global Operators

I/O

Types

Iterators

Creation

Modifiers

Access Functions

Predicates

Convenience Orientation Functions

Random Access Methods

Miscellaneous

Constructor & Destructor Documentation

◆ Polygon_2()

Member Function Documentation

◆ area()

◆ bottom_vertex()

◆ bounded_side()

◆ edges_begin()

◆ edges_circulator()

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ left_vertex()

◆ operator<<()

◆ operator==()

◆ operator>>()

◆ orientation()

◆ oriented_side()

◆ reverse_orientation()

◆ right_vertex()

◆ set()

◆ top_vertex()

◆ vertices_begin()

◆ vertices_circulator()

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