Class

CGAL::Polygon_2<PolygonTraits_2, Container>

Definition

The class Polygon_2<PolygonTraits_2, Container> implements polygons. The Polygon_2<PolygonTraits_2, Container> 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 vector class.

#include <CGAL/Polygon_2.h>

Types

Polygon_2<PolygonTraits_2, Container>::Traits
The traits type.

Polygon_2<PolygonTraits_2, Container>::Container
The container type.

typedef Traits::FT FT; The number type, which is the field type 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.

The following types denote iterators that allow to traverse the vertices and edges of a polygon. Since it is questionable whether a polygon should be viewed as a circular or as a linear data structure both circulators and iterators are defined. The circulators and iterators are non-mutable.1 The iterator category is in all cases bidirectional, except for Vertex_iterator, which has the same iterator category as Container::iterator. N.B. In fact all of them should have the same iterator category as Container::iterator. However, due to compiler problems this is currently not possible.

For vertices we define

Polygon_2<PolygonTraits_2, Container>::Vertex_iterator
Polygon_2<PolygonTraits_2, Container>::Vertex_circulator

Their value type is Point_2.

For edges we define

Polygon_2<PolygonTraits_2, Container>::Edge_const_circulator
Polygon_2<PolygonTraits_2, Container>::Edge_const_iterator

Their value type is Segment_2.

Creation

Polygon_2<PolygonTraits_2, Container> pgn ( Traits p_traits = Traits());
Creates an empty polygon pgn.


template <class InputIterator>
Polygon_2<PolygonTraits_2, Container> pgn ( InputIterator first, InputIterator last, Traits p_traits = Traits());
Introduces a polygon pgn with vertices from the sequence defined by the range [first,last). The value type of InputIterator must be Point_2.

Modifiers

void pgn.set ( Vertex_iterator pos, Point_2 x)
Acts as *pos = x, except that that would be illegal because the iterator is not mutable.

Vertex_iterator pgn.insert ( Vertex_iterator i, Point_2 q)
Inserts the vertex q before i. The return value points to the inserted vertex.

template <class InputIterator>
void pgn.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 pgn.push_back ( Point_2 q) Has the same semantics as p.insert(p.vertices_end(), q).

void pgn.erase ( Vertex_iterator i) Erases the vertex pointed to by i.

void pgn.erase ( Vertex_iterator first, Vertex_iterator last)
Erases the vertices in the range [first, last).

void pgn.clear () Erases all vertices.

void pgn.reverse_orientation () Reverses the orientation of the polygon. The vertex pointed to by p.vertices_begin() remains the same.

Access Functions

The following methods of the class Polygon_2 return circulators and iterators that allow to traverse the vertices and edges.

Vertex_iterator pgn.vertices_begin () const Returns a constant iterator that allows to traverse the vertices of the polygon pgn.

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

Vertex_circulator pgn.vertices_circulator () const Returns a mutable circulator that allows to traverse the vertices of the polygon pgn.

Edge_const_iterator pgn.edges_begin () const Returns a non-mutable iterator that allows to traverse the edges of the polygon pgn.

Edge_const_iterator pgn.edges_end () const Returns the corresponding past-the-end iterator.

Edge_const_circulator pgn.edges_circulator () const Returns a non-mutable circulator that allows to traverse the edges of the polygon pgn.

Predicates

bool pgn.is_simple () const Returns whether pgn is a simple polygon.

bool pgn.is_convex () const Returns whether pgn is convex.

Orientation pgn.orientation () const Returns the orientation of pgn. If the number of vertices p.size() < 3 then COLLINEAR is returned.
Precondition: p.is_simple().

Oriented_side pgn.oriented_side ( Point_2 q) const
Returns POSITIVE_SIDE, or NEGATIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is.
Precondition: p.is_simple().

Bounded_side pgn.bounded_side ( Point_2 q) const
Returns the symbolic constant ON_BOUNDED_SIDE, ON_BOUNDARY or ON_UNBOUNDED_SIDE, depending on where point q is.
Precondition: p.is_simple().

Bbox_2 pgn.bbox () const Returns the smallest bounding box containing pgn.

Traits::FT pgn.area () const Returns the signed area of the polygon pgn. This means that the area is positive for counter clockwise polygons and negative for clockwise polygons.

Vertex_iterator pgn.left_vertex () Returns the leftmost vertex of the polygon pgn with the smallest x-coordinate.

Vertex_iterator pgn.right_vertex () Returns the rightmost vertex of the polygon pgn with the largest x-coordinate.

Vertex_iterator pgn.top_vertex () Returns topmost vertex of the polygon pgn with the largest y-coordinate.

Vertex_iterator pgn.bottom_vertex () Returns the bottommost vertex of the polygon pgn with the smallest y-coordinate.

For convenience we provide the following Boolean functions:

bool pgn.is_counterclockwise_oriented () const
bool pgn.is_clockwise_oriented () const

bool pgn.is_collinear_oriented () const
bool pgn.has_on_positive_side ( Point_2 q) const
bool pgn.has_on_negative_side ( Point_2 q) const
bool pgn.has_on_boundary ( Point_2 q) const
bool pgn.has_on_bounded_side ( Point_2 q) const
bool pgn.has_on_unbounded_side ( Point_2 q) const

Random access methods

These methods are only available for random access containers.

Point_2 pgn.vertex ( std::size_t i) const Returns a (const) reference to the i-th vertex.

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

Segment_2 pgn.edge ( std::size_t i) const Returns the i-th edge.

Miscellaneous

std::size_t pgn.size () const Returns the number of vertices of the polygon pgn.

bool pgn.is_empty () const Returns p.size() == 0.

Container pgn.container () const Returns a const reference to the sequence of vertices of the polygon pgn.

Globally defined operators

template <class Traits, class Container1, class Container2>

bool Polygon_2<Traits,Container1> p1 == Polygon_2<Traits,Container2> 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, class Container1, class Container2>

bool Polygon_2<Traits,Container1> p1 != Polygon_2<Traits,Container2> p2
Test for inequality.

template <class Transformation, class Traits, class Container>

Polygon_2<Traits,Container> transform ( Transformation t, Polygon_2<Traits,Container> p)
Returns the image of the polygon p under the transformation t.

I/O

The I/O operators are defined for iostream. The format for the iostream is an internal format.

ostream& ostream& os << Polygon_2<Traits,Container> p
Inserts the polygon pgn into the stream os.
Precondition: The insert operator must be defined for Point_2.

istream& istream& is >> Polygon_2<Traits,Container> p
Reads a polygon from stream is and assigns it to pgn.
Precondition: The extract operator must be defined for Point_2.

The information output in the iostream is the number of points followed by the output of the coordinates of the vertices.

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.

Example

The following code fragment creates a polygon and checks if it is convex.

File: examples/Polygon/Polygon.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;
using std::cout; using std::endl;


int main()
{
  Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
  Polygon_2 pgn(points, points+4);

  // check if the polygon is simple.
  cout << "The polygon is " <<
    (pgn.is_simple() ? "" : "not ") << "simple." << endl;

  // check if the polygon is convex
  cout << "The polygon is " <<
    (pgn.is_convex() ? "" : "not ") << "convex." << endl;

  return 0;
}


Footnotes

 1  At least conceptually. The enforcement depends on preprocessor flags.