next up previous contents index
Next: Triangles ( triangle ) Up: Basic Data Types for Previous: Polygons ( POLYGON )   Contents   Index


Generalized Polygons ( GEN_POLYGON )

Definition

There are three instantiations of POLYGON: gen_polygon (floating point kernel), rat_gen_polygon (rational kernel) and real_gen_polygon (real kernel). The respective header file name corresponds to the type name (with ``.h'' appended).

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 P1, P2, ..., Pk of a GEN_POLYGON are ordered such that no Pi is nested in a Pj with i < j.

Only the types rat_polygon and real_polygon guarantee correct results. Almost all operations listed below are available for all the three instantiations of POLYGON. There is a small number of operations that are only available for polygon, they are indicated as such.

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/geo/generic/GEN_POLYGON.h >

Types

GEN_POLYGON::coord_type the coordinate type (e.g. rational).

GEN_POLYGON::point_type the point type (e.g. rat_point).

GEN_POLYGON::segment_type the segment type (e.g. rat_segment).

GEN_POLYGON::polygon_type the polygon type (e.g. rat_polygon).

GEN_POLYGON::float_type the corresponding floating-point type (gen_polygon).

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(const 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(const list<POINT>& pl, CHECK_TYPE check= GEN_POLYGON::WEAKLY_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(const 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(const list<GEN_POLYGON>& PL)
    introduces a variable P of type GEN_POLYGON. P is initialized to the union of all generalized polygons in PL.

GEN_POLYGON P(const 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.

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

KIND P.kind() returns the kind of P.

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

void P.normalize() simplifies the homogenous representation by calling p.normalize() for every vertex p 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 GEN_POLYGON::check_representation(const list<POLYGON>& PL)
    checks whether PL is a boundary representation.

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.
Please note that it is not save to use this function in a forall-loop. Instead of writing forall(SEGMENT s, edges()).. please write list<SEGMENT> L = edges(); forall(SEGMENT s, L)....

const list<POLYGON>& P.polygons() returns the lists of all polygons in the boundary representation of P.

list<POINT> P.intersection(const SEGMENT& s)
    returns the list of all proper intersections between s and the boundary of P.

list<POINT> P.intersection(const 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(const VECTOR& v)
    returns P translated by vector v.

GEN_POLYGON P + const VECTOR& v returns P translated by vector v.

GEN_POLYGON P - const VECTOR& v returns P translated by vector - v.

GEN_POLYGON P.rotate90(const POINT& q, int i=1)
    returns P rotated about q by an angle of i x 90 degrees. If i > 0 the rotation is counter-clockwise otherwise it is clockwise.

GEN_POLYGON P.reflect(const POINT& p, const POINT& q)
    returns P reflected across the straight line passing through p and q.

GEN_POLYGON P.reflect(const POINT& p) returns P reflected across point p.

RAT_TYPE P.sqr_dist(const 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.

GEN_POLYGON P.make_weakly_simple(bool with_neg_parts = true, bool strict = false)
    creates a weakly simple generalized polygon Q from a possibly non-simple polygon P such that Q and P have the same inner points. The flag with_neg_parts determines whether inner points in negatively oriented parts are taken into account, too. If strict is true a point is considered an inner point if it is left of all surrounding segments, otherwise it is considered as an inner point if it is locally to the left of some surrounding edge. (This function is experimental.)

GEN_POLYGON GEN_POLYGON::make_weakly_simple(const POLYGON& Q, bool with_neg_parts = true, bool strict = false)
    same as above but the input is a polygon Q. (This function is experimental.)

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

GEN_POLYGON P.eliminate_colinear_vertices()
    returns a copy of P without colinear vertices.

int P.side_of(const 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(const 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(const POINT& p) returns true if p lies to the left of P, i.e., side_of(p) == +1.

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

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

bool P.contains(const 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. Precondition P is not the full polygon.

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

list<GEN_POLYGON> P.regional_decomposition()
    computes a decomposition of the bounded region of P into simple connected components P1,..., Pn. If P is trivial the decomposition is P itself. Otherwise, the boundary of every Pi consists of an exterior polygon and zero or more holes nested inside. But the holes do not contain any nested polygons. (Note that P may have holes containing nested polygons; they appear as seperate components in the decomposition.) Every Pi has the same orientation as P. If it is positive then P is the union of P1,..., Pn, otherwise P is the intersection of P1,..., Pn.

GEN_POLYGON P.buffer(RAT_TYPE d, int p = 3)
    adds an exterior buffer zone to P (d > 0), or removes an interior buffer zone from P (d < 0). More precisely, for d > = 0 define the buffer tube T as the set of all points in the complement of P whose distance to P is at most d. Then the function returns P $\cup$ T. For d < 0 let T denote the set of all points in P whose distance to the complement is less than | d|. Then the result is P $\setminus$ T. p specifies the number of points used to represent convex corners. At the moment, only p = 1 and p = 3 are supported. (This function is experimental.)

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(const GEN_POLYGON& Q)
    returns reg(P $\cup$ Q).

GEN_POLYGON P.intersection(const GEN_POLYGON& Q)
    returns reg(P $\cap$ Q).

GEN_POLYGON P.diff(const GEN_POLYGON& Q)
    returns reg(P $\setminus$ Q).

GEN_POLYGON P.sym_diff(const GEN_POLYGON& Q)
    returns reg((P $\cup$ Q) - (P $\cap$ Q)).

The following functions are only available for gen_polygons. They have no counterpart for rat_gen_polygons or real_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(const point& p, double alpha)
    returns P rotated by $\alpha$ degrees about p.

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

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

rat_gen_polygon P.to_rational(int prec = -1)
    returns a representation of P with rational coordinates with precision prec (cf. Section Rational Points).


Iterations Macros

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


next up previous contents index
Next: Triangles ( triangle ) Up: Basic Data Types for Previous: Polygons ( POLYGON )   Contents   Index