CGAL 5.6.1 - 2D Polygons
CGAL::Polygon_2< Traits_P, Container_P > Class Template Reference

#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, Polygon/Polygon.cpp, and Polygon/ranges.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 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.

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

Polygon_2 (Polygon_2< Traits_P, Container_P > &&polygon)=default
Move 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_iterator vertices_begin () const
Returns a constant iterator that allows to traverse the vertices of the polygon. More...

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

const Verticesvertices () const
returns the range of vertices.

Vertex_circulator vertices_circulator () const
Returns a constant 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.

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. 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 the 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_2vertex (std::size_t i) const
Returns a (const) reference to the i-th vertex.

const Point_2operator[] (std::size_t i) const
Returns a (const) reference to the i-th vertex.

Point_2vertex (std::size_t i)
Returns a reference to the i-th vertex.

Point_2operator[] (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).

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

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

## ◆ 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 the 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_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_circulator CGAL::Polygon_2< Traits_P, Container_P >::vertices_circulator ( ) const

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

## ◆ operator<<()

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

Inserts the polygon p into the stream os.

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 )
related

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

Precondition
The extract operator must be defined for Point_2.