Generalized Polygons ( GEN_POLYGON )

Definition

There are two instantiations of GEN_POLYGON. The instantiation with the rational kernel is called rat_gen_polygon and requires inclusion of rat_gen_polygon.h and the instantiation with the floating point kernel is called gen_polygon and requires inclusion of gen_polygon.h.

An instance P of the data type GEN_POLYGON is a regular polygonal region in the plane. A regular region is an open set that is equal to the interior of its closure. A region is polygonal if its boundary consists of a finite number of line segments.

The boundary of a GEN_POLYGON consists of zero or more weakly simple closed polygonal chains. There are two regions whose boundary is empty, namely the empty region and the full region. The full region encompasses the entire plane. We call a region non-trivial if its boundary is non-empty. The boundary cycles P₁, P₂, ..., P_k of a GEN_POLYGON are ordered such that no P_j is nested in a P_i with i < j.

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

A detailed discussion of polygons and generalized polygons can be found in the LEDA book.

The local enumeration type KIND consists of elements EMPTY, FULL, and NON_TRIVIAL.

#include < LEDA/generic/GEN _POLYGON.h >

Creation

GEN_POLYGON	P(KIND k = GEN_POLYGON_REP::EMPTY)
		introduces a variable P of type GEN_POLYGON. P is initialized to the empty polygon if k is EMPTY and to the full polygon if k is FULL.
GEN_POLYGON	P(POLYGON p, CHECK_TYPE check = WEAKLY_SIMPLE, RESPECT_TYPE respect_orientation = RESPECT_ORIENTATION)
		introduces a variable P of type GEN_POLYGON. P is initialized to the polygonal region with boundary p. If respect_orientation is DISREGARD_ORIENTATION, the orientation is chosen such P is bounded. Precondition: p must be a weakly simple polygon. If check is set appropriately this is checked.
GEN_POLYGON	P(list<POINT> pl, CHECK_TYPE check= GEN_POLYGON::SIMPLE, RESPECT_TYPE respect_orientation = RESPECT_ORIENTATION)
		introduces a variable P of type GEN_POLYGON. P is initialized to the polygon with vertex sequence pl. If respect_orientation is DISREGARD_ORIENTATION, the orientation is chosen such that P is bounded. 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 three constants NO_CHECK, SIMPLE, and WEAKLY_SIMPLE are part of a local enumeration type CHECK_TYPE.
GEN_POLYGON	P(list<POLYGON> PL, CHECK_TYPE check = CHECK_REP)
		introduces a variable P of type GEN_POLYGON. P is initialized to the polygon with boundary representation PL. Precondition: PL must be a boundary representation. This conditions is checked if check is set to CHECK_REP.
GEN_POLYGON	P(gen_polygon Q, int prec = rat_point::default_precision)
		introduces a variable P of type GEN_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

bool	P.empty()	returns true if P is empty, false otherwise.
bool	P.full()	returns true if P is the entire plane, false otherwise.
bool	P.trivial()	returns true if P is either empty or full, false otherwise.
KIND	P.kind()	returns the kind of P.
gen_polygon	P.to_gen_polygon()	returns a floating point approximation of P.
bool	P.is_simple()	returns true if the polygonal region is simple, i.e., if the graph defined by the segments in the boundary of P has only vertices of degree two.
bool	P.check_representation()	tests whether the representation of P is OK. This test is partial.
void	P.canonical_rep()	NOT IMPLEMENTED YET.
list<POINT>	P.vertices()	returns the concatenated vertex lists of all polygons in the boundary representation of P.
list<SEGMENT>	P.edges()	returns the concatenated edge lists of all polygons in the boundary representation of P.
list<POLYGON>	P.polygons()	returns the lists of all polygons in the boundary representation of P.
list<POINT>	P.intersection(SEGMENT s)	returns the list of all proper intersections between s and the boundary of P.
list<POINT>	P.intersection(LINE l)	returns the list of all proper intersections between l and the boundary of P.
int	P.size()	returns the number of segments in the boundary of P.
GEN_POLYGON	P.translate(RAT_TYPE dx, RAT_TYPE dy)
		returns P translated by vector (dx, dy).
GEN_POLYGON	P.translate(INT_TYPE dx, INT_TYPE dy, INT_TYPE dw)
		returns P translated by vector (dx/dw, dy/dw).
GEN_POLYGON	P.translate(VECTOR v)	returns P translated by vector v.
GEN_POLYGON	P + VECTOR v	returns P translated by vector v.
GEN_POLYGON	P - VECTOR v	returns P translated by vector - v.
GEN_POLYGON	P.rotate90(POINT q)	returns P rotated by 90 degrees about q.
GEN_POLYGON	P.reflect(POINT p, POINT q)
		returns P reflected across the straight line passing through p and q.
GEN_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 the boundary of P and p. Returns zero is P is trivial.
	()	returns the simple parts of P as a list of simple polygons. WAS MACH ICH DAMIT.
GEN_POLYGON	P.complement()	returns the complement of 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. The bounded region of the full polygon is the entire plane.
bool	P.inside(POINT p)	returns true if p lies to the left of P.
bool	P.outside(POINT p)	returns true if p lies to the right of P.
bool	P.on_boundary(POINT p)	returns true if p lies on P, i.e., region_of(p) == ON_REGION
bool	P.contains(POINT p)	returns true if p does not lie in the unbounded region of 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. Precondition: P is not the full polygon.

All binary boolean operations are regularized, i.e., the result R of the standard boolean operation is replaced by the interior of the closure of R. We use regX to denote the regularization of a set X.

GEN_POLYGON	P.unite(GEN_POLYGON Q)	returns reg(P < union > Q).
GEN_POLYGON	P.intersection(GEN_POLYGON Q)
		returns reg(P < intersection > Q).
GEN_POLYGON	P.diff(GEN_POLYGON Q)	returns reg(P $\setminus$ Q).
GEN_POLYGON	P.sym_diff(GEN_POLYGON Q)	returns reg((P < union > Q) - (P < intersection > Q)).

The following functions are only available for gen_polygons. They have no counterpart for rat_gen_polygons.

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

Iterations Macros

forall_polygons(p, P) { ``the boundary polygons of P are successively assigned to POLYGON p'' }