Next: Parser for well known Up: Basic Data Types for Previous: Polygons with circular edges   Contents   Index

# Generalized polygons with circular edges ( r_circle_gen_polygon )

Definition

The data type r_circle_polygon is not closed under boolean operations, e.g., the set difference of a polygon P and a polygon Q nested in P is a region that contains a hole''. Therefore we provide a generalization called r_circle_gen_polygon which is closed under (regularized) boolean operations (see below).

A formal definition follows: An instance P of the data type r_circle_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 r_circle_segments.

The boundary of an r_circle_gen_polygon consists of zero or more weakly simple closed polygonal chains. Each such chain is represented by an object of type r_circle_ploygon. 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 trivial if its boundary is empty. The boundary cycles P1, P2, ..., Pk of an r_circle_gen_polygon are ordered such that no Pi is nested in a Pj with i < j.

#include < LEDA/geo/r_circle_gen_polygon.h >

Types

 r_circle_gen_polygon::coord_type the coordinate type (real). r_circle_gen_polygon::point_type the point type (r_circle_point). r_circle_gen_polygon::segment_type the segment type (r_circle_segment). r_circle_gen_polygon::polygon_type the polygon type (r_circle_polygon). r_circle_gen_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_gen_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_gen_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_gen_polygon P creates an empty polygon P. r_circle_gen_polygon P(KIND k) creates a polygon P of kind k, where k is either EMPTY or FULL. r_circle_gen_polygon P(const list& seg_chain, CHECK_TYPE check = WEAKLY_SIMPLE, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION) creates a polygon P from a single closed chain of segments. r_circle_gen_polygon P(const r_circle_polygon& Q, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION) converts an r_circle_polygon Q to an r_circle_gen_polygon P. r_circle_gen_polygon P(const list& L, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION) creates a polygon P with straight line edges from a list L of vertices. r_circle_gen_polygon P(const list& polys, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION) introduces a variable P of type r_circle_gen_polygon. P is initialized to the polygon with boundary representation polys. Precondition polys must be a boundary representation. r_circle_gen_polygon P(const list& gen_polys) creates a polygon P as the union of all the polygons in gen_polys. Precondition Every polygon in gen_polys must be weakly simple. r_circle_gen_polygon P(const rat_gen_polygon& Q, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION) converts a rat_gen_polygon Q to an r_circle_gen_polygon P. r_circle_gen_polygon P(const gen_polygon& Q, CHECK_TYPE check = NO_CHECK, RESPECT_TYPE respect_orient = RESPECT_ORIENTATION, int prec = rat_point::default_precision) converts the (floating point) gen_polygon Q to an r_circle_gen_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_gen_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 full. void P.normalize() simplifies the representation by calling c.normalize() for every polygonal chain c 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& crossings) as above, returns all proper points of intersection in crossings. bool r_circle_gen_polygon::check_representation(const list& polys, CHECK_TYPE check = WEAKLY_SIMPLE) checks whether polys is a boundary representation. Currently the nesting order is not checked, we check only for (weak) simplicity. bool P.check_representation() checks the representation of P (see above). bool P.is_convex() returns true iff P is convex. int P.size() returns the size of P, i.e. the number of segments in its boundary representation. const list& P.polygons() returns the boundary representation of P. list P.edges() returns a chain of segments that bound P. The orientation of the chain corresponds to the orientation of P. list P.vertices() returns the vertices of P. list P.intersection(const r_circle_segment& s) returns the list of all proper intersections between s and the boundary of P. list P.intersection(const rat_line& l) returns the list of all proper intersections between l and the boundary of P. r_circle_gen_polygon P.translate(rational dx, rational dy) returns P translated by vector (dx, dy). r_circle_gen_polygon P.translate(const rat_vector& v) returns P translated by vector v. r_circle_gen_polygon P + const rat_vector& v returns P translated by vector v. r_circle_gen_polygon P - const rat_vector& v returns P translated by vector - v. r_circle_gen_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_gen_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_gen_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.) 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_gen_polygon r_circle_gen_polygon::make_weakly_simple(const r_circle_polygon& Q) same as above, but the input is a polygon Q. (This function is experimental.) r_circle_gen_polygon P.complement() returns the complement of P. r_circle_gen_polygon P.contour() returns the contour of P, i.e. all holes are removed from P. r_circle_gen_polygon P.eliminate_cocircular_vertices() returns a copy of P without cocircular vertices. r_circle_gen_polygon P.round(int prec = 0) returns a rounded representation of P. (experimental) bool P.is_r_circle_polygon() checks if the boundary of P consists of at most one chain. r_circle_polygon P.to_r_circle_polygon() converts P to an r_circle_polygon. Precondition is_r_circle_polygon is true. bool P.is_rat_gen_polygon() returns whether P can be converted to a rat_polygon. rat_gen_polygon P.to_rat_gen_polygon() converts P to a rat_gen_polygon. Precondition is_rat_gen_polygon is true. rat_gen_polygon P.approximate_by_rat_gen_polygon(double dist) approximates P by a rat_gen_polygon. The maxmum distance between a point on P and the approximation is bounded by dist. gen_polygon P.to_float() computes a floating point approximation of P with straight line segments. Precondition is_rat_gen_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. The bounded region of the full polygon is the entire plane. 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.

All 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.

 r_circle_gen_polygon P.unite(const r_circle_gen_polygon& Q) returns reg(P Q). r_circle_gen_polygon P.intersection(const r_circle_gen_polygon& Q) returns reg(P Q). r_circle_gen_polygon P.diff(const r_circle_gen_polygon& Q) returns reg(P Q). r_circle_gen_polygon P.sym_diff(const r_circle_gen_polygon& Q) returns reg((P Q) - (P Q)).

For optimization purposes we provide a union operation of arbitrary arity. It computes the union of a set of polygons much faster than with binary operations.

 r_circle_gen_polygon r_circle_gen_polygon::unite(const list& L) returns the (regularized) union of all polygons in L.

We offer fast versions of the boolean operations which compute an approximate result. These operations work as follows: every curved segment is approximated by straight line segments, then the respective boolean operation is performed on the straight polygons. Finally, we identify those straight segments in the result that originate from a curved segment and replace them by curved segments again. (We denote the approximate computation of an operation op scheme by appr(op). ) Every operation below takes a parameter dist that controls the accuracy of the approximation: dist is an upper bound on the distance of any point on an original polygon P to the approximated polygon P'.

 r_circle_gen_polygon P.unite_approximate(const r_circle_gen_polygon& Q, double dist = 1e-2) returns appr(P Q). r_circle_gen_polygon P.intersection_approximate(const r_circle_gen_polygon& Q, double dist = 1e-2) returns appr(P Q). r_circle_gen_polygon P.diff_approximate(const r_circle_gen_polygon& Q, double dist = 1e-2) returns appr(P Q). r_circle_gen_polygon P.sym_diff_approximate(const r_circle_gen_polygon& Q, double dist = 1e-2) returns appr((P Q) - (P Q)). r_circle_gen_polygon r_circle_gen_polygon::unite_approximate(const list& L, double dist = 1e-2) returns the (approximated) union of all polygons in L. r_circle_gen_polygon P.buffer(double d) 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.

Iterations Macros

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

Next: Parser for well known Up: Basic Data Types for Previous: Polygons with circular edges   Contents   Index