CGAL 6.1 - 2D Polygons

Loading...
Searching...
No Matches
List of all members
CGAL::Polygon_2< Traits_, Container_ > Class Template Reference
Reference Manual

`#include <CGAL/Polygon_2.h>`

## Definition

template<class Traits_, class Container_ = std::vector<typename Traits_::Point_2>>
class CGAL::Polygon_2< Traits_, Container_ >

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_ | Container
| The container type.
typedef Traits_::FT | FT
| The number type of the coordinates of the points of the polygon.
typedef Traits_::Point_2 | Point_2
| The point type of the polygon.
typedef Traits_::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_ & | container () const
| Returns a const reference to the sequence of vertices of the polygon.
Container_ & | container ()
| Returns a reference to the sequence of vertices of the polygon.
Container_::iterator | begin ()
| Returns an iterator to the first vertex of the polygon.
Container_::iterator | end ()
| Returns an iterator to the element after the last vertex of the polygon.
const Container_::const_iterator | begin () const
| Returns a const iterator to the first vertex of the polygon.
const Container_::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_ , class Container1_P , class Container2_P >
bool | operator== (const Polygon_2< Traits_, Container1_P > &p1, const Polygon_2< Traits_, 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_ , class Container1_P , class Container2_P >
bool | operator!= (const Polygon_2< Traits_, Container1_P > &p1, const Polygon_2< Traits_, Container2_P > &p2)
| Test for inequality.
template<class Transformation , class Traits_ , class Container_ >
Polygon_2< Traits_, Container_ > | transform (const Transformation &t, const Polygon_2< Traits_, Container_ > &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_ , class Container_ >
std::istream & | operator>> (std::istream &is, Polygon_2< Traits_, Container_ > &p)
| Reads a polygon from stream `is` and assigns it to `p`.
template<class Traits_ , class Container_ >
std::ostream & | operator<< (std::ostream &os, const Polygon_2< Traits_, Container_ > &p)
| Inserts the polygon `p` into the stream `os`.

## Constructor & Destructor Documentation

## ◆ Polygon_2()

template<class Traits_ , class Container_ = std::vector<typename Traits_::Point_2>>
template<class InputIterator >

CGAL::Polygon_2< Traits_, Container_ >::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_ , class Container_ = std::vector<typename Traits_::Point_2>>

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.

## ◆ bounded_side()

template<class Traits_ , class Container_ = std::vector<typename Traits_::Point_2>>

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

## ◆ insert() [1/4]

template<class Traits_ , class Container_ = std::vector<typename Traits_::Point_2>>

Vertex_iterator CGAL::Polygon_2< Traits_, Container_ >::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_ , class Container_ = std::vector<typename Traits_::Point_2>>
template<class InputIterator >

void CGAL::Polygon_2< Traits_, Container_ >::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_ , class Container_ = std::vector<typename Traits_::Point_2>>

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.

## ◆ insert() [4/4]

template<class Traits_ , class Container_ = std::vector<typename Traits_::Point_2>>
template<class InputIterator >

void CGAL::Polygon_2< Traits_, Container_ >::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_ , class Container1_P , class Container2_P >

bool operator== | ( | const Polygon_2< Traits_, Container1_P > & | p1,
|  | const Polygon_2< Traits_, 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_ , class Container_ = std::vector<typename Traits_::Point_2>>

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

## ◆ oriented_side()

template<class Traits_ , class Container_ = std::vector<typename Traits_::Point_2>>

Oriented_side CGAL::Polygon_2< Traits_, Container_ >::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_ , class Container_ = std::vector<typename Traits_::Point_2>>

void CGAL::Polygon_2< Traits_, Container_ >::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_ , class Container_ >

std::ostream & operator<< | ( | std::ostream & | os,
|  | const Polygon_2< Traits_, Container_ > & | p
| ) |  |
| related

Inserts the polygon `p` into the stream `os`.

Precondition
  The insert operator must be defined for `Point_2`.

## ◆ operator>>()

template<class Traits_ , class Container_ >

std::istream & operator>> | ( | std::istream & | is,
|  | Polygon_2< Traits_, Container_ > & | p
| ) |  |
| related

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

Precondition
  The extract operator must be defined for `Point_2`.