Polygons ( POLYGON )

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

POLYGON::coord_type	the coordinate type (e.g. rational).
POLYGON::point_type	the point type (e.g. rat_point).
POLYGON::segment_type	the segment type (e.g. rat_segment).
POLYGON::float_type	the corresponding floating-point type (polygon).

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 counter-clockwise ordering.
const list<SEGMENT>&	P.segments()	returns the sequence of bounding segments of P in counter-clockwise 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 $\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.)

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 $\alpha$ degrees about p.
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_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.

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.
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.
int	P.orientation()	returns the orientation of P.
void	P.bounding_box(POINT& xmin, POINT& ymin, POINT& xmax, POINT& ymax)
		returns the coordinates of a rectangular bounding box 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.