next up previous contents index
Next: Generalized polygons with circular Up: Basic Data Types for Previous: Segment of Rational Circle   Contents   Index


Polygons with circular edges ( r_circle_polygon )

Definition

An instance P of the data type r_circle_polygon is a cyclic list of r_circle_segments, i.e. straight line or circular segments. 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 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 segments is called the size of P. A polygon of size zero is trivial; it either describes the empty set or the full two-dimensional plane.

#include < LEDA/geo/r_circle_polygon.h >

Types

r_circle_polygon::coord_type the coordinate type (real).

r_circle_polygon::point_type the point type (r_circle_point).

r_circle_polygon::segment_type the segment type (r_circle_segment).

r_circle_polygon::KIND { EMPTY, FULL, NON_TRIVIAL }
  describes the kind of the polygon: the empty set, the full plane or a non-trivial polygon.

r_circle_polygon::CHECK_TYPE { NO_CHECK, SIMPLE, WEAKLY_SIMPLE, NOT_WEAKLY_SIMPLE }
  used to specify which checks should be applied and also describes the outcome of a simplicity check.

r_circle_polygon::RESPECT_TYPE { DISREGARD_ORIENTATION, RESPECT_ORIENTATION }
  used in contructors to specify whether to force a positive orientation for the constructed object (DISREGARD_ORIENTATION) or to keep the orientation of the input (RESPECT_ORIENTATION).

Creation

r_circle_polygon P creates an empty polygon P.

r_circle_polygon P(KIND k) creates a polygon P of kind k, where k is either EMPTY or FULL.

r_circle_polygon P(const list<r_circle_segment>& chain, CHECK_TYPE check = WEAKLY_SIMPLE, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION)
    creates a polygon P from a closed chain of segments.

r_circle_polygon P(const list<rat_point>& L, CHECK_TYPE check = WEAKLY_SIMPLE, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION)
    creates a polygon P with straight line edges from a list L of vertices.

r_circle_polygon P(const rat_polygon& Q, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION)
    converts a rat_polygon Q to an r_circle_polygon P.

r_circle_polygon P(const polygon& Q, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION, int prec = rat_point::default_precision)
    converts the (floating point) polygon Q to an r_circle_polygon. P is initialized to a rational approximation of 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.

r_circle_polygon P(const rat_circle& circ, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION)
    creates a polygon P whose boundary is the circle circ.

Operations

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

bool P.is_trivial() returns true iff P is trivial.

bool P.is_empty() returns true iff P is empty.

bool P.is_full() returns true iff P is the full plane.

void P.normalize() simplifies the representation by calling s.normalize() for every segment s of P.

bool P.is_closed_chain() tests whether P is a closed chain.

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

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

bool P.is_weakly_simple(list<r_circle_point>& crossings)
    as above, returns all proper points of intersection in crossings.

CHECK_TYPE P.check_simplicity() checks P for simplicity. The result can be SIMPLE, WEAKLY_SIMPLE or NOT_WEAKLY_SIMPLE.

bool P.is_convex() returns true iff P is convex.

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

const list<r_circle_segment>& P.segments() returns a chain of segments that bound P. The orientation of the chain corresponds to the orientation of P.

list<r_circle_point> P.vertices() returns the vertices of P.

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

list<r_circle_point> P.intersection(const rat_line& l)
    returns the list of all proper intersections between l and the boundary of P.

r_circle_polygon P.intersection_halfplane(const rat_line& l)
    clips P against the halfplane on the positive side of l. Observe that the result is only guaranteed to be weakly simple if P is convex.

r_circle_polygon P.translate(rational dx, rational dy)
    returns P translated by vector (dx, dy).

r_circle_polygon P.translate(const rat_vector& v)
    returns P translated by vector v.

r_circle_polygon P + const rat_vector& v returns P translated by vector v.

r_circle_polygon P - const rat_vector& v returns P translated by vector - v.

r_circle_polygon P.rotate90(const rat_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.

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

r_circle_polygon P.reflect(const rat_point& p)
    returns P reflected across point p.

real P.sqr_dist(const real_point& p)
    computes the squared Euclidean distance between the boundary of P and p. (If P is zero, the result is zero.)

real P.dist(const real_point& p)
    computes the Euclidean distance between the boundary of P and p. (If P is zero, the result is zero.)

list<r_circle_polygon> P.split_into_weakly_simple_parts()
    splits P into a set of weakly simple polygons whose union coincides with the inner points of P. (This function is experimental.)

r_circle_gen_polygon P.make_weakly_simple() creates a weakly simple generalized polygon Q from a possibly non-simple polygon P such that Q and P have the same inner points. (This function is experimental.)

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

r_circle_polygon P.eliminate_cocircular_vertices()
    returns a copy of P without cocircular vertices.

r_circle_polygon P.round(int prec = 0) returns a rounded representation of P. (experimental)

bool P.is_rat_polygon() returns whether P can be converted to a rat_polygon.

rat_polygon P.to_rat_polygon() converts P to a rat_polygon.
Precondition is_rat_polygon is true.

rat_polygon P.approximate_by_rat_polygon(double dist)
    approximates P by a rat_polygon. The maxmum distance between a point on P and the approximation is bounded by dist.

polygon P.to_float() computes a floating point approximation of P with straight line segments.
Precondition is_rat_polygon is true.

bool P.is_rat_circle() returns whether P can be converted to a rat_circle.

rat_circle P.to_rat_circle() converts P to a rat_circle.
Precondition is_rat_circle is true.

void P.bounding_box(real& xmin, real& ymin, real& xmax, real& ymax)
    computes a tight bounding box for P.

void P.bounding_box(double& xmin, double& ymin, double& xmax, double& ymax)
    computes a bounding box for P, but not necessarily a tight one.


All functions below assume that P is weakly simple.


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

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

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

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

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

double P.approximate_area() approximates the (oriented) area of the bounded region of P.
Precondition P.kind() is not full.

r_circle_gen_polygon buffer(double d) adds an exterior buffer zone to P (if d > 0), or removes an interior buffer zone from P (if 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. Note that the result is a generalized polygon since the buffer of a connected polygon may be disconnected, i.e. consist of several parts, if d < 0.


Iterations Macros

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

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


next up previous contents index
Next: Generalized polygons with circular Up: Basic Data Types for Previous: Segment of Rational Circle   Contents   Index
root 2008-01-09