2D Polygon (CGAL_Polygon_2)

Definition

An object p of the data type CGAL_Polygon_2 is defined by the sequence of its vertices. A polygon p is oriented, i.e., its boundary has clockwise or counterclockwise orientation. We call the side to the left of the boundary the positive side and the side to the right of the boundary 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 CGAL_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 all predicates of polygons.

The data type CGAL_Polygon_2 is parametrized with two template parameters: a traits class Traits and a container class Container. The most important task of the parameter Traits is to specify the type of the points stored in the polygon. The default point type is CGAL_Point_2<Traits>. 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 [Musser & al. 96]. The value type of the container should be the same as the point type of the traits class. N.B. Due to compiler problems, the only container that is currently guaranteed to work correctly is the STL-container list. (To be more specific: the circulators and iterators that are used to traverse the vertices and edges currently have a fixed iterator category and a fixed distance type. As a consequence, sometimes the wrong version of an STL algorithm will be selected. This problem will be solved in the near future by using iterator traits.)

Note: Currently, a polygon declaration looks like CGAL_Polygon_2<Traits, list<Traits::Point> >. When nested templates become available this might be simplified to CGAL_Polygon_2<Traits, list>.

Types

CGAL_Polygon_2<Traits,Container>::Traits
	The traits type.

typedef Traits::Point	Point;
typedef Traits::Segment	Segment;
typedef Traits::Triangle	Triangle;
typedef Traits::Iso_rectangle
	Iso_rectangle;

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, which has the same iterator category as Container::iterator. N.B. As mentioned before, in fact all of them should have the same iterator category as Container::iterator. This will be changed when iterator traits become available.

For vertices we define

CGAL_Polygon_2<Traits,Container>::Vertex_circulator

CGAL_Polygon_2<Traits,Container>::Vertex_const_circulator

CGAL_Polygon_2<Traits,Container>::Vertex_iterator

CGAL_Polygon_2<Traits,Container>::Vertex_const_iterator

Their value type is Point.

For edges we define

CGAL_Polygon_2<Traits,Container>::Edge_const_circulator

CGAL_Polygon_2<Traits,Container>::Edge_const_iterator

Their value type is Segment.

Creation

template <class InputIterator>
CGAL_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 first and last is Point.
CGAL_Polygon_2<Traits,Container> p ( int n);
	Introduces a polygon p with n uninitialized vertices. This constructor is supplied for efficiency reasons.
CGAL_Polygon_2<Traits,Container> p ( Point q);
	Introduces a polygon p with one vertex q.
CGAL_Polygon_2<Traits,Container> p ( Segment s);
	Introduces a polygon p with two vertices from segment s.
CGAL_Polygon_2<Traits,Container> p ( Triangle t);
	Introduces a polygon p with three vertices from triangle t, with the same orientation.
CGAL_Polygon_2<Traits,Container> p ( Iso_rectangle rectangle r);
	Introduces a polygon p with four vertices from rectangle r, having counterclockwise orientation.

Operations

The following operations allow to modify a polygon.

Vertex_iterator	p.insert ( Vertex_iterator i, Point q)
		Inserts the vertex q before i. The return value points to the inserted vertex.
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 first and last is Point.
void	p.append ( Point q)	Has the same semantics as p.insert(p.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

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

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.
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.
Edge_const_circulator	p.edges_circulator ()	Returns a non-mutable circulator that allows to traverse the edges 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.

Predicates

bool	p.is_simple ()	Returns whether p is a simple polygon.
bool	p.is_convex ()	Returns whether p is convex.
CGAL_Orientation	p.orientation ()	Returns the orientation of p. If the number of vertices $$p.size() then CGAL_COLLINEAR is returned. Precondition: p.is_simple().
CGAL_Oriented_side	p.oriented_side ( Point q)
		Returns CGAL_POSITIVE_SIDE, CGAL_NEGATIVE_SIDE, or CGAL_ON_ORIENTED_BOUNDARY, depending on where point q is. Precondition: p.is_simple().
CGAL_Bounded_side	p.bounded_side ( Point q)
		Returns the symbolic constant CGAL_ON_BOUNDED_SIDE, CGAL_ON_BOUNDARY or CGAL_ON_UNBOUNDED_SIDE, depending on where point q is. Precondition: p.is_simple().
CGAL_Bbox_2	p.bbox ()	Returns the smallest bounding box containing p.
Traits::FT	p.area ()	Returns the area of the polygon p. Precondition: p.is_simple().
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 q)
bool	p.has_on_negative_side ( Point q)
bool	p.has_on_boundary ( Point q)
bool	p.has_on_bounded_side ( Point q)
bool	p.has_on_unbounded_side ( Point q)

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.
CGAL_Polygon_2<Traits,Container>
	p.transform ( CGAL_Aff_transformation_2<Traits> t)
		Returns the polygon obtained by applying the transformation t to the vertices of p.

template <class Traits, class Container1, class Container2>

bool	CGAL_Polygon_2<Traits,Container1> p1 == CGAL_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	CGAL_Polygon_2<Traits,Container1> p1 != CGAL_Polygon_2<Traits,Container2> p2
		Test for inequality.

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.

#include <CGAL/IO/ostream_2.h>

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

Example

typedef CGAL_Cartesian<double> Traits;
typedef CGAL_Point_2<Traits> Point;
typedef CGAL_Polygon_2<Traits, list<Point> > Polygon;

{
  Polygon p;

  while(cin) {
    Point q;
    cin >> q;
    p.append(q);
  }

  cout << "The polygon you entered is ";
  if (!p.is_convex())
    cout << "not ";
  cout << "convex.";
}

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 functions on sequences of 2D points described below. There you can find information on the algorithms that were used and their complexity.