\( \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 4.4 - 2D Polygons
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Polygon_2< _Traits, _Container > Class Template Reference

#include <CGAL/Polygon_2.h>

Definition

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. 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, 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)
 Inserts the polygon p into the stream os. More...
 
template<class Traits_P , class Container_P >
std::ostream & operator<< (std::ostream &os, const Polygon_2< Traits_P, Container_P > &p)
 Reads a polygon from stream is and assigns it to p. 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
 
typedef unspecified_type Vertex_circulator
 
typedef unspecified_type Edge_const_iterator
 
typedef unspecified_type Edge_const_circulator
 

Creation

 Polygon_2 (const Traits &p_traits=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())
 Introduces 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...
 
void set (Polygon_circulator< Container >const &i, const Point_2 &q)
 
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)
 

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 POSITIVE_SIDE, or 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...
 

For convenience we provide the following Boolean functions:

bool is_counterclockwise_oriented () const
 
bool is_clockwise_oriented () const
 
bool is_collinear_oriented () const
 
bool has_on_positive_side (const Point_2 &q) const
 
bool has_on_negative_side (const Point_2 &q) const
 
bool has_on_boundary (const Point_2 &q) const
 
bool has_on_bounded_side (const Point_2 &q) const
 
bool has_on_unbounded_side (const Point_2 &q) const
 

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

Constructor & Destructor Documentation

template<class _Traits , class _Container >
template<class InputIterator >
CGAL::Polygon_2< _Traits, _Container >::Polygon_2 ( InputIterator  first,
InputIterator  last,
Traits  p_traits = Traits() 
)

Introduces 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

template<class _Traits , class _Container >
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.

template<class _Traits , class _Container >
Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::bottom_vertex ( ) const

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

template<class _Traits , class _Container >
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().
template<class _Traits , class _Container >
Edge_const_iterator CGAL::Polygon_2< _Traits, _Container >::edges_begin ( ) const

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

template<class _Traits , class _Container >
Edge_const_circulator CGAL::Polygon_2< _Traits, _Container >::edges_circulator ( ) const

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

template<class _Traits , class _Container >
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.

template<class _Traits , class _Container >
Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::left_vertex ( ) const

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

template<class Traits_P , class Container_P >
std::ostream & operator<< ( std::ostream &  os,
const 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.
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.

template<class Traits_P , class Container_P >
std::istream & operator>> ( std::istream &  is,
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.
template<class _Traits , class _Container >
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().
template<class _Traits , class _Container >
Oriented_side CGAL::Polygon_2< _Traits, _Container >::oriented_side ( const Point_2 value) const

Returns POSITIVE_SIDE, or NEGATIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is.

Precondition
p.is_simple().
template<class _Traits , class _Container >
Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::right_vertex ( ) const

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

template<class _Traits , class _Container >
void CGAL::Polygon_2< _Traits, _Container >::set ( Vertex_iterator  i,
const Point_2 q 
)

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

template<class _Traits , class _Container >
Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::top_vertex ( ) const

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

template<class _Traits , class _Container >
Vertex_const_iterator CGAL::Polygon_2< _Traits, _Container >::vertices_begin ( ) const

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

template<class _Traits , class _Container >
Vertex_const_circulator CGAL::Polygon_2< _Traits, _Container >::vertices_circulator ( ) const

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