2D Polygon (Polygon_2)

Definition

The class Polygon_2 represents a simple polygon in the two-dimensional Euclidean plane $$ ₂. A polygon is called simple if there is no pair of nonconsecutive edges sharing a point (see [PS85]).

An object p of the data type Polygon_2 is defined by the sequence of its vertices. A simple polygon p is oriented, i.e., its boundary has clockwise or counterclockwise orientation. The side to the left of the boundary is called the positive side and the side to the right of the boundary is called the negative side. As any Jordan curve, the boundary of a polygon divides the plane into two open regions, a bounded one and an unbounded one.

An object p of Polygon_2 is a dynamic data structure, i.e. vertices can be added and removed. These operations may destroy the simplicity of the polygon, which is a precondition to most predicates of polygons.

The data type Polygon_2 is parameterized with two template parameters: a traits class Traits and a container class Container. The parameter Traits defines the types and predicates that are used in the polygon class and the polygon algorithms. For example Traits::Point_2 denotes the type of the vertices of the polygon. A default polygon traits class Polygon_traits_2<R> is provided (see Section ), where R is a representation class. The parameter Container specifies the type of container that is used to store the sequence of vertices of the polygon, e.g. a list, a vector, a tree, etc. The type Container should fulfill the requirements of a sequence container given in [MS96]. The value type of the container should be the same as the point type of the traits class.

Assertions

Types

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 with `const' in their name are non-mutable, the others are mutable. The iterator category is in all cases bidirectional, except for Vertex_iterator and Vertex_const_iterator, which have 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. This will be corrected when iterator traits become available. The consequence of using iterators / circulators with an incorrect iterator category is that when an STL algorithm is applied to such a range, the wrong (i.e. inefficient) version of an STL algorithm may be selected.

For vertices we define

Polygon_2<Traits,Container>::Vertex_iterator

Polygon_2<Traits,Container>::Vertex_const_iterator

Polygon_2<Traits,Container>::Vertex_circulator

Polygon_2<Traits,Container>::Vertex_const_circulator

Their value type is Point_2.

For edges we define

Polygon_2<Traits,Container>::Edge_const_circulator

Polygon_2<Traits,Container>::Edge_const_iterator

Their value type is Segment_2.

Creation

template <class InputIterator>
Polygon_2<Traits,Container> p ( InputIterator first, InputIterator last);
	Introduces a polygon p with vertices from the sequence defined by the range [first,last). Precondition: The value type of points in the range [first,last) is Point_2.
template <class ForwardCirculator>
Polygon_2<Traits,Container> p ( ForwardCirculator start);
	Introduces a polygon p with vertices from the sequence defined by the range [start,start]. Precondition: The value type of points in the range [first,last) is Point_2.

Operations

The following operations allow to modify a polygon.

Vertex_iterator	p.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	p.insert ( Vertex_iterator i, InputIterator first, InputIterator last)
		Inserts the vertices in the range [first, last) before i. Precondition: The value type of points in the range [first,last) is Point_2.
void	p.push_back ( Point_2 q)
		Has the same semantics as p.insert(p.vertices_end(), q).
void	p.erase ( Vertex_iterator i)
		Erases the vertex pointed to by i.
void	p.erase ( Vertex_iterator first, Vertex_iterator last)
		Erases the vertices in the range [first, last).
void	p.reverse_orientation ()
		Reverses the orientation of the polygon. The vertex pointed to by p.vertices_begin() remains the same.

Traversal of a polygon

Vertex_iterator	p.vertices_begin ()
		Returns a mutable iterator that allows to traverse the vertices of the polygon p.
Vertex_iterator	p.vertices_end ()	Returns the corresponding past-the-end iterator.
Vertex_const_iterator
	p.vertices_begin ()
		Returns a non-mutable iterator that allows to traverse the vertices of the polygon p.
Vertex_const_iterator
	p.vertices_end ()	Returns the corresponding past-the-end iterator.
Vertex_circulator	p.vertices_circulator ()
		Returns a mutable circulator that allows to traverse the vertices of the polygon p.
Vertex_const_circulator
	p.vertices_circulator ()
		Returns a non-mutable circulator that allows to traverse the vertices of the polygon p.
Edge_const_iterator
	p.edges_begin ()	Returns a non-mutable iterator that allows to traverse the edges of the polygon p.
Edge_const_iterator
	p.edges_end ()	Returns the corresponding past-the-end iterator.
Edge_const_circulator
	p.edges_circulator ()
		Returns a non-mutable circulator that allows to traverse the edges of the polygon p.

Predicates

bool	p.is_simple ()	Returns whether p is a simple polygon.
bool	p.is_convex ()	Returns whether p is convex.
Orientation	p.orientation ()	Returns the orientation of p. If the number of vertices $$p.size() < 3 then COLLINEAR is returned. Precondition: p.is_simple().
Oriented_side	p.oriented_side ( Point_2 q)
		Returns POSITIVE_SIDE, or NEGATIVE_SIDE, or ON_ORIENTED_BOUNDARY, depending on where point q is. Precondition: p.is_simple().
Bounded_side	p.bounded_side ( Point_2 q)
		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	p.bbox ()	Returns the smallest bounding box containing p.
Traits::FT	p.area ()	Returns the signed area of the polygon p. This means that the area is positive for counter clockwise polygons and negative for clockwise polygons.
Vertex_iterator	p.left_vertex ()	Returns the leftmost vertex of the polygon p with the smallest y-coordinate.
Vertex_iterator	p.right_vertex ()	Returns the rightmost vertex of the polygon p with the largest y-coordinate.
Vertex_iterator	p.top_vertex ()	Returns topmost vertex of the polygon p with the largest x-coordinate.
Vertex_iterator	p.bottom_vertex ()	Returns the bottommost vertex of the polygon p with the smallest x-coordinate.

For convenience we provide the following boolean functions:

bool	p.is_counterclockwise_oriented ()
bool	p.is_clockwise_oriented ()
bool	p.is_collinear_oriented ()
bool	p.has_on_positive_side ( Point_2 q)
bool	p.has_on_negative_side ( Point_2 q)
bool	p.has_on_boundary ( Point_2 q)
bool	p.has_on_bounded_side ( Point_2 q)
bool	p.has_on_unbounded_side ( Point_2 q)

Random access methods

Point_2	p.vertex ( int i)	Returns a (const) reference to the $$i-th vertex.
Point_2	p [ int i]	Returns a (const) reference to the $$i-th vertex.
Segment_2	p.edge ( int i)	Returns a const reference to the $$i-th edge.

Miscellaneous

int	p.size ()	Returns the number of vertices of the polygon p.
bool	p.is_empty ()	Returns $$p.size() == 0.
Container	p.container ()	Returns a const reference to the sequence of vertices of the polygon p.

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, p)
		Returns the image of the polygon p under the transformation t.

I/O

The I/O operators are defined for iostream, and for the window stream provided by CGAL. The format for the iostream is an internal format.

ostream&	ostream& os << Polygon_2<Traits, Container> p
		Inserts the polygon p into the stream os. Precondition: The insert operator is defined for class Point_2.
istream&	istream& is >> Polygon_2<Traits, Container> p
		Reads a polygon from stream is and assigns it to p.

#include <CGAL/IO/Window_stream.h>

Window_stream&	Window_stream& W << Polygon_2<Traits, Container> p
		Inserts the triangulation p into the window stream W. The insert operator must be defined for Point_2.

Example

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

#include <CGAL/basic.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Polygon_2.h>
#include <list>

typedef CGAL::Cartesian<double> R;
typedef CGAL::Polygon_traits_2<R> Traits;
typedef Traits::Point_2 Point;
typedef std::list<Point> Container;
typedef CGAL::Polygon_2<Traits,Container> Polygon;

#include <iostream>

int main()
{
  Polygon p;

  p.push_back(Point(0,0));
  p.push_back(Point(1,0));
  p.push_back(Point(1,1));
  p.push_back(Point(0,1));

  cout << "The polygon is " << (p.is_convex() ? "" : "not ") << "convex." << endl;

  return 0;
}

Implementation