\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 5.0 - 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, 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_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).
 

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.