Next: Generalized Polygons ( GEN_POLYGON Up: Basic Data Types for Previous: Circles ( circle ) Contents Index

Polygons ( POLYGON )

Definition

There are two instantiations of POLYGON. The instantiation with the rational kernel is called rat_polygon and requires inclusion of rat_polygon.h and the instantiation with the floating point kernel is called polygon and requires inclusion of polygon.h.

An instance P of the data type POLYGON is a cyclic list of points (equivalently segments) in the plane. A polygon is called simple if all nodes of the graph induced by its segments have degree two and it is called weakly simple, if its segments are disjoint except for common endpoints and if the chain does not cross itself. See the LEDA book for more details.

A weakly simple polygon splits the plane into an unbounded region and one or more bounded regions. For a simple polygon there is just one bounded region. When a weakly simple polygon P is traversed either the bounded region is consistently to the left of P or the unbounded region is consistently to the left of P. We say that P is positively oriented in the former case and negatively oriented in the latter case. We use P to also denote the region to the left of P and call this region the positive side of P.

The number of vertices is called the size of P. A polygon with empty vertex sequence is called empty.

There are two instantiations of POLYGONS, namely rat_polygon and polygon. Only the former guarantee correct results. All operations for rat_polygon are also available for polygon. There is a small number of operations that are only available for polygon.

#include < LEDA/generic/POLYGON.h >

Types

POLYGON::coord_type the coordinate type (rational).

POLYGON::point_type the point type (rat_point).

POLYGON::float_type the corresponding floatin-point type (polygon).

Creation

POLYGON P introduces a variable P of type POLYGON. P is initialized to the empty polygon.

POLYGON P(list<POINT> pl, CHECK_TYPE check= POLYGON::SIMPLE, RESPECT_TYPE respect_orientation = POLYGON::RESPECT_ORIENTATION)

introduces a variable P of type POLYGON. P is initialized to the polygon with vertex sequence pl. If respect_orientation is DISREGARD_ORIENTATION, the positive orientation is chosen.
Precondition If check is SIMPLE, pl must define a simple polygon, and if check is WEAKLY_SIMPLE, pl must define a weakly simple polygon. If no test is to performed, the second argument has to be set to NO_CHECK. The constants NO_CHECK, SIMPLE, and WEAKLY_SIMPLE are part of a local enumeration type CHECK_TYPE.

POLYGON P(polygon Q, int prec = rat_point::default_precision)

introduces a variable P of type POLYGON. P is initialized to a rational approximation of the (floating point) polygon Q of coordinates with denominator at most prec. If prec is zero, the implementation chooses prec large enough such that there is no loss of precision in the conversion.

Operations

polygon P.to_float() returns a floating point approximation of P.

bool P.is_simple() tests whether P is simple or not.

bool P.is_weakly_simple() tests whether P is weakly simple or not.

list<POINT> P.vertices() returns the sequence of vertices of P in counterclockwise ordering.

list<SEGMENT> P.segments() returns the sequence of bounding segments of P in counterclockwise ordering.

list<POINT> P.intersection(SEGMENT s) returns the proper crossings between P and s as a list of points.

list<POINT> P.intersection(LINE l) returns the proper crossings between P and l as a list of points.

POLYGON P.intersect_halfplane(LINE l)

returns the intersection of P with the halfspace on the positive side of l.

int P.size() returns the size of P.

bool P.empty() returns true if P is empty, false otherwise.

POLYGON P.translate(RAT_TYPE dx, RAT_TYPE dy)

returns P translated by vector (dx, dy).

POLYGON P.translate(INT_TYPE dx, INT_TYPE dy, INT_TYPE dw)

returns P translated by vector (dx/dw, dy/dw).

POLYGON P.translate(VECTOR v) returns P translated by vector v.

POLYGON P + VECTOR v returns P translated by vector v.

POLYGON P - VECTOR v returns P translated by vector - v.

POLYGON P.rotate90(POINT q) returns P rotated by 90 degrees about q.

POLYGON P.reflect(POINT p, POINT q)

returns P reflected across the straight line passing through p and q.

POLYGON P.reflect(POINT p) returns P reflected across point p.

RAT_TYPE P.sqr_dist(POINT p) returns the square of the minimal Euclidean distance between a segment in P and p. Returns zero if P is empty.

list<POLYGON> P.simple_parts() returns the simple parts of P as a list of simple polygons. WHAT TO DO WITH IT.

POLYGON P.complement() returns the complement of P.

The functions in the following group are only available for polygons. They have no counterpart for rat_polygons.

polygon P.translate_by_angle(double alpha, double d)

returns P translated in direction alpha by distance d.

polygon P.rotate(point p, double alpha)

returns P rotated by $\alpha$ degrees about p.

polygon P.rotate(double alpha) returns P rotated by $\alpha$ degrees about the origin.

double P.distance(point p) returns the Euclidean distance between P and p.

All functions below assume that P is weakly simple.

int P.side_of(POINT p) returns +1 if p lies to the left of P, 0 if p lies on P, and -1 if p lies to the right of P.

region_kind P.region_of(POINT p) returns BOUNDED_REGION if p lies in the bounded region of P, returns ON_REGION if p lies on P, and returns UNBOUNDED_REGION if p lies in the unbounded region.

bool P.inside(POINT p) returns true if p lies to the left of P, i.e., side_of(p) == +1.

bool P.on_boundary(POINT p) returns true if p lies on P, i.e., side_of(p) == 0.

bool P.outside(POINT p) returns true if p lies to the right of P, i.e., side_of(p) == -1.

bool P.contains(POINT p) returns true if p lies to the left of or on P.

RAT_TYPE P.area() returns the signed area of the bounded region of P. The sign of the area is positive if the bounded region is the positive side of P.

int P.orientation() returns the orientation of P.

Iterations Macros

forall_vertices(v, P) { ``the vertices of P are successively assigned to rat_point v'' }

forall_segments(s, P) { ``the edges of P are successively assigned to rat_segment s'' }

Non-Member Functions

POLYGON reg_n_gon(int n, CIRCLE C, double epsilon)

generates a (nearly) regular n-gon whose vertices lie on the circle C. The i-th point is generated by C.point $\_$ of $\_$ circle(2 $\pi$ i/n, epsilon). With the rational kernel the vertices of the n-gon are guaranteed to lie on the circle, with the floating point kernel they are only guaranteed to lie near C.

POLYGON n_gon(int n, CIRCLE C, double epsilon)

generates a (nearly) regular n-gon whose vertices lie near the circle C. For the flaoting point kernel the function is equivalent to the function above. For the rational kernel the function first generates a n-gon with floating point arithmetic and then converts the resulting polygon to a rat_polygon.

POLYGON hilbert(int n, RAT_TYPE x1, RAT_TYPE y1, RAT_TYPE x2, RAT_TYPE y2)

generates the Hilbert polygon of order n within the rectangle with boundary (x1, y1) and (x2, y2).
Precondition x1 < x2 and y1 < y2.

Next: Generalized Polygons ( GEN_POLYGON Up: Basic Data Types for Previous: Circles ( circle ) Contents Index

LEDA research project
2000-02-09

POLYGON::coord_type	the coordinate type (rational).
POLYGON::point_type	the point type (rat_point).
POLYGON::float_type	the corresponding floatin-point type (polygon).

POLYGON	P	introduces a variable P of type POLYGON. P is initialized to the empty polygon.
POLYGON	P(list<POINT> pl, CHECK_TYPE check= POLYGON::SIMPLE, RESPECT_TYPE respect_orientation = POLYGON::RESPECT_ORIENTATION)
		introduces a variable P of type POLYGON. P is initialized to the polygon with vertex sequence pl. If respect_orientation is DISREGARD_ORIENTATION, the positive orientation is chosen. Precondition If check is SIMPLE, pl must define a simple polygon, and if check is WEAKLY_SIMPLE, pl must define a weakly simple polygon. If no test is to performed, the second argument has to be set to NO_CHECK. The constants NO_CHECK, SIMPLE, and WEAKLY_SIMPLE are part of a local enumeration type CHECK_TYPE.
POLYGON	P(polygon Q, int prec = rat_point::default_precision)
		introduces a variable P of type POLYGON. P is initialized to a rational approximation of the (floating point) polygon Q of coordinates with denominator at most prec. If prec is zero, the implementation chooses prec large enough such that there is no loss of precision in the conversion.

polygon	P.to_float()	returns a floating point approximation of P.
bool	P.is_simple()	tests whether P is simple or not.
bool	P.is_weakly_simple()	tests whether P is weakly simple or not.
list<POINT>	P.vertices()	returns the sequence of vertices of P in counterclockwise ordering.
list<SEGMENT>	P.segments()	returns the sequence of bounding segments of P in counterclockwise ordering.
list<POINT>	P.intersection(SEGMENT s)	returns the proper crossings between P and s as a list of points.
list<POINT>	P.intersection(LINE l)	returns the proper crossings between P and l as a list of points.
POLYGON	P.intersect_halfplane(LINE l)
		returns the intersection of P with the halfspace on the positive side of l.
int	P.size()	returns the size of P.
bool	P.empty()	returns true if P is empty, false otherwise.
POLYGON	P.translate(RAT_TYPE dx, RAT_TYPE dy)
		returns P translated by vector (dx, dy).
POLYGON	P.translate(INT_TYPE dx, INT_TYPE dy, INT_TYPE dw)
		returns P translated by vector (dx/dw, dy/dw).
POLYGON	P.translate(VECTOR v)	returns P translated by vector v.
POLYGON	P + VECTOR v	returns P translated by vector v.
POLYGON	P - VECTOR v	returns P translated by vector - v.
POLYGON	P.rotate90(POINT q)	returns P rotated by 90 degrees about q.
POLYGON	P.reflect(POINT p, POINT q)
		returns P reflected across the straight line passing through p and q.
POLYGON	P.reflect(POINT p)	returns P reflected across point p.
RAT_TYPE	P.sqr_dist(POINT p)	returns the square of the minimal Euclidean distance between a segment in P and p. Returns zero if P is empty.
list<POLYGON>	P.simple_parts()	returns the simple parts of P as a list of simple polygons. WHAT TO DO WITH IT.
POLYGON	P.complement()	returns the complement of P.

polygon	P.translate_by_angle(double alpha, double d)
		returns P translated in direction alpha by distance d.
polygon	P.rotate(point p, double alpha)
		returns P rotated by $\alpha$ degrees about p.
polygon	P.rotate(double alpha)	returns P rotated by $\alpha$ degrees about the origin.
double	P.distance(point p)	returns the Euclidean distance between P and p.

int	P.side_of(POINT p)	returns +1 if p lies to the left of P, 0 if p lies on P, and -1 if p lies to the right of P.
region_kind	P.region_of(POINT p)	returns BOUNDED_REGION if p lies in the bounded region of P, returns ON_REGION if p lies on P, and returns UNBOUNDED_REGION if p lies in the unbounded region.
bool	P.inside(POINT p)	returns true if p lies to the left of P, i.e., side_of(p) == +1.
bool	P.on_boundary(POINT p)	returns true if p lies on P, i.e., side_of(p) == 0.
bool	P.outside(POINT p)	returns true if p lies to the right of P, i.e., side_of(p) == -1.
bool	P.contains(POINT p)	returns true if p lies to the left of or on P.
RAT_TYPE	P.area()	returns the signed area of the bounded region of P. The sign of the area is positive if the bounded region is the positive side of P.
int	P.orientation()	returns the orientation of P.

POLYGON	reg_n_gon(int n, CIRCLE C, double epsilon)
		generates a (nearly) regular n-gon whose vertices lie on the circle C. The i-th point is generated by C.point $\_$ of $\_$ circle(2 $\pi$ i/n, epsilon). With the rational kernel the vertices of the n-gon are guaranteed to lie on the circle, with the floating point kernel they are only guaranteed to lie near C.
POLYGON	n_gon(int n, CIRCLE C, double epsilon)
		generates a (nearly) regular n-gon whose vertices lie near the circle C. For the flaoting point kernel the function is equivalent to the function above. For the rational kernel the function first generates a n-gon with floating point arithmetic and then converts the resulting polygon to a rat_polygon.
POLYGON	hilbert(int n, RAT_TYPE x1, RAT_TYPE y1, RAT_TYPE x2, RAT_TYPE y2)
		generates the Hilbert polygon of order n within the rectangle with boundary (x1, y1) and (x2, y2). Precondition x1 < x2 and y1 < y2.