Definition
There are three instantiations of POLYGON: polygon (floating point kernel), rat_polygon (rational kernel) and real_polygon (real kernel). The respective header file name corresponds to the type name (with ``.h'' appended).
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.
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.
#include < LEDA/geo/generic/POLYGON.h >
Types
Creation
POLYGON | P | introduces a variable P of type POLYGON. P is initialized to the empty polygon. |
POLYGON | P(const list< POINT> & pl, CHECK_TYPE check= POLYGON::WEAKLY_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(const 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. |
void | P.normalize() | simplifies the homogenous representation by calling p.normalize() for every vertex p 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. |
bool | P.is_weakly_simple(list< POINT> & L) | |
as above, returns all proper points of intersection in L. | ||
POLYGON::CHECK_TYPE | P.check_simplicity() | returns the CHECK_TYPE of P. The result can be SIMPLE, WEAKLY_SIMPLE or NOT_WEAKLY_SIMPLE. |
bool | P.is_convex() | returns true if P is convex, false otherwise. |
const list< POINT> & | P.vertices() | returns the sequence of vertices of P in counterclockwise ordering. |
const list< SEGMENT> & | P.segments() | returns the sequence of bounding segments of P in counterclockwise ordering. |
list< POINT> | P.intersection(const SEGMENT& s) | |
returns the proper crossings between P and s as a list of points. | ||
list< POINT> | P.intersection(const LINE& l) | |
returns the proper crossings between P and l as a list of points. | ||
POLYGON | P.intersect_halfplane(const 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(const VECTOR& v) | |
returns P translated by vector v . | ||
POLYGON | P + const VECTOR& v | returns P translated by vector v . |
POLYGON | P - const VECTOR& v | returns P translated by vector - v . |
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. | ||
POLYGON | P.reflect(const POINT& p, const POINT& q) | |
returns P reflected across the straight line passing through p and q . | ||
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 P and p . Returns zero if P is empty. | ||
POLYGON | P.complement() | returns the complement of P . |
POLYGON | P.eliminate_colinear_vertices() | |
returns a copy of P without colinear vertices. | ||
list< POLYGON> | P.simple_parts() | returns the simple parts of P as a list of simple polygons. |
list< POLYGON> | P.split_into_weakly_simple_parts(bool strict = false) | |
splits P into a set of weakly simple polygons whose union coincides with the inner points of P . 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 | 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. The meaning of the flag strict is the same as in the method above. (This function is experimental.) | ||
GEN_POLYGON | P.buffer(RAT_TYPE d, int p) | |
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 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 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.) |
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(const point& p, double alpha) | |
returns P rotated by degrees about p . | ||
polygon | P.rotate(double alpha) | returns P rotated by degrees about the origin. |
double | P.distance(const point& p) | |
returns the Euclidean distance between P and p . | ||
rat_polygon | P.to_rational(int prec = -1) | |
returns a representation of P with rational coordinates with precision prec (cf. Section Rational Points). |
All functions below assume that P
is weakly simple.
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