CGAL 5.0 - 2D Polygons
|
#include <CGAL/Polygon_2.h>
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.
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 | |
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.
| |
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 | |
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) . | |
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
.
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.
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 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.
p.is_simple()
. 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.
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.
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.
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.
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
.
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
.
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.
std::ostream & operator<< | ( | std::ostream & | os, |
const Polygon_2< Traits_P, Container_P > & | p | ||
) |
Inserts the polygon p
into the stream os
.
Point_2
. 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.
std::istream & operator>> | ( | std::istream & | is, |
Polygon_2< Traits_P, Container_P > & | p | ||
) |
Reads a polygon from stream is
and assigns it to 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.
p.is_simple()
. 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.
p.is_simple()
. 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.
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.
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.
Vertex_const_iterator CGAL::Polygon_2< Traits_P, Container_P >::top_vertex | ( | ) | const |
Returns topmost vertex of the polygon with the largest y
-coordinate.
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.
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.