The class
Polygon_2
represents a simple polygon in the two-dimensional
Euclidean plane
2
. 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
The polygon code uses infix
POLYGON
in the assertions,
for example defining the compiler flag
CGAL_POLYGON_NO_PRECONDITIONS
switches precondition
checking off, cf. Section 2 of the Reference Manual Part 0, General
Introduction.
Types
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
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
.
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
.
Returns the orientation of
p
. If the number of vertices
p.size()
< 3
then
COLLINEAR
is returned.
Precondition:
p.is_simple()
.
Returns
POSITIVE_SIDE
, or
NEGATIVE_SIDE
,
or
ON_ORIENTED_BOUNDARY
,
depending on where point
q
is.
Precondition:
p.is_simple()
.
Returns the symbolic constant
ON_BOUNDED_SIDE
,
ON_BOUNDARY
or
ON_UNBOUNDED_SIDE
, depending on where point
q
is.
Precondition:
p.is_simple()
.
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.
The I/O operators are defined for
iostream
, and for
the window stream provided by C
GAL
. The format for the iostream
is an internal format.
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
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 described
in section
. There you can find information about which
algorithms were used and what their complexity they have.
Next:
Class declaration of
Polygon_traits
