Next: Polygons with circular edges Up: Basic Data Types for Previous: Point on Rational Circle   Contents   Index

# Segment of Rational Circle ( r_circle_segment )

Definition

An instance cs of type r_circle_segment is a segment of a rational circle (see Section rat_circle), i.e. a circular arc. A segment is called trivial if it consists of a single point. A non-trivial instance cs is defined by two points s and t (of type r_circle_point) and an oriented circle c (of type rat_circle) such that c contains both s and t. We call s and t the source and the target of cs, and c is called its supporting circle. We want to point out that the circle may be a line, which means that cs is a straight line segment. An instance cs is called degenerate, if it is trivial or a straight line segment.

#include < LEDA/geo/r_circle_segment.h >

Creation

 r_circle_segment cs creates a trivial instance cs with source and target equal to the point (0, 0). r_circle_segment cs(const r_circle_point& src, const r_circle_point& tgt, const rat_circle& c) creates an instance cs with source src, target tgt and supporting circle c. Precondition src! = tgt, c is not trivial and contains src and tgt. r_circle_segment cs(const r_circle_point& src, const r_circle_point& tgt, const rat_line& l) creates an instance cs with source src, target tgt and supporting line l. Precondition src! = tgt, l contains src and tgt. r_circle_segment cs(const rat_point& src, const rat_point& middle, const rat_point& tgt) creates an instance cs with source src and target tgt which passes through middle. Precondition the three points are distinct. r_circle_segment cs(const r_circle_point& p) creates a trivial instance cs with source and target equal to p. r_circle_segment cs(const rat_point& rat_pnt) creates a trivial instance cs with source and target equal to rat_pnt. r_circle_segment cs(const rat_circle& c) creates an instance cs which is equal to the full circle c. Precondition c is not degenerate. r_circle_segment cs(const rat_point& src, const rat_point& tgt) creates an instance cs which is equal to the straight line segment from src to tgt. r_circle_segment cs(const rat_segment& s) creates an instance cs which is equal to the straight line segment s. r_circle_segment cs(const r_circle_point& src, const r_circle_point& tgt) creates an instance cs which is equal to the straight line segment from src to tgt. Precondition Both src and tgt are rat_points.

Operations

 void cs.normalize() simplifies the internal representation of cs. const r_circle_point& cs.source() returns the source of cs. const r_circle_point& cs.target() returns the target of cs. const rat_circle& cs.circle() returns the supporting circle of cs. rat_line cs.supporting_line() returns a line containing cs. Precondition cs is a straight line segment. rat_point cs.center() returns the center of the supporting circle of cs. int cs.orientation() returns the orientation (of the supporting circle) of cs. real_point cs.real_middle() returns the middle point of cs, i.e. the intersection of cs and the bisector of its source and target. r_circle_point cs.middle() returns a point on the circle of cs, which is close to real_middle(). bool cs.is_trivial() returns true iff cs is trivial. bool cs.is_degenerate() returns true iff cs is degenerate. bool cs.is_full_circle() returns true iff cs is a full circle. bool cs.is_proper_arc() returns true iff cs is a proper arc, i.e. neither degenerate nor a full circle. bool cs.is_straight_segment() returns true iff cs is a straight line segment. bool cs.is_vertical_segment() returns true iff cs is a vertical straight line segment. bool cs.is_rat_segment() returns true, if cs can be converted to rat_segment. (The value false means do not know''.) rat_segment cs.to_rat_segment() converts cs to a rat_segment. Precondition is_rat_segment returns true. bool cs.contains(const r_circle_point& p) returns true iff cs contains p. bool cs.overlaps(const r_circle_segment& cs2) returns true iff cs (properly) overlaps cs2. bool cs.wedge_contains(const real_point& p) returns true iff the (closed) wedge induced by cs contains p. This wedge is spanned by the rays which start at the center and pass through source and target. (Note that p belongs to cs iff p is on the supporting circle and the wedge contains p.) r_circle_segment cs.reverse() returns the reversal of cs, i.e. source and target are swapped and the supporting circle is reversed. r_circle_segment cs.round(int prec = 0) returns a rounded representation of cs. (experimental) r_circle_segment cs.translate(rational dx, rational dy) returns cs translated by vector (dx, dy). r_circle_segment cs.translate(const rat_vector& v) returns cs translated by vector v. r_circle_segment cs + const rat_vector& v returns cs translated by vector v. r_circle_segment cs - const rat_vector& v returns cs translated by vector - v. r_circle_segment cs.rotate90(const rat_point& q, int i=1) returns cs 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_segment cs.reflect(const rat_point& p, const rat_point& q) returns cs reflected across the straight line passing through p and q. r_circle_segment cs.reflect(const rat_point& p) returns cs reflected across point p. list cs.intersection(const rat_line& l) computes cs l (ordered along l). list cs.intersection(const real_line& l) as above. list cs.intersection(const rat_circle& c) computes cs c (ordered lexicographically). list cs.intersection(const r_circle_segment& cs2) computes cs cs2 (ordered lexicographically). real cs.sqr_dist(const real_point& p) computes the squared Euclidean distance between cs and p. real cs.dist(const real_point& p) computes the euclidean distance between cs and p. real_line cs.tangent_at(const r_circle_point& p) computes the tanget to cs at p. Precondition cs is not trivial. double cs.approximate_area() computes the (oriented) area enclosed by the convex hull of cs. void cs.compute_bounding_box(real& xmin, real& ymin, real& xmax, real& ymax) computes a tight bounding box for cs. list cs.approximate(double dist) approximates cs by a sequence of points. Connecting the points with straight line segments yields a chain with the following property: The maximum distance from a point on cs to the chain is bounded by dist. list cs.approximate_by_rat_points(double dist) as above, returns rat_points instead of points. list cs.approximate_by_rat_segments(double dist) approximates cs by a chain of rat_segments. The maximum distance from a point on cs to the chain is bounded by dist. bool equal_as_sets(const r_circle_segment& cs1, const r_circle_segment& cs2) returns whether cs1 and cs2 describe the same set of points. int compare_tangent_slopes(const r_circle_segment& cs1, const r_circle_segment& cs2, const r_circle_point& p) compares the slopes of the tangents to cs1 and cs2 in the point p. Precondition cs1 and cs2 contain p.

We provide the operator « to display an instance cs of type r_circle_segment in a window and the operator » for reading cs from a window (see real_window.h).

 void SWEEP_SEGMENTS(const list& L, GRAPH& G, bool embed = true) takes as input a list L of r_circle_segments and computes the planar graph G induced by the segments in L. The nodes of G are all endpoints and all proper intersection points of segments in L. The edges of G are the maximal relatively open subsegments of segments in L that contain no node of G. The edges are directed as the corresponding segments, if embed is false. Otherwise, the corresponding planar map is computed. Note that for each edge e G[e] is the input segment containing e. The algorithm (a variant of [11]) runs in time O((n + s)log n) + m), where n is the number of segments, s is the number of vertices of the graph G, and m is the number of edges of G. If L contains no overlapping segments then m = O(n + s).

Next: Polygons with circular edges Up: Basic Data Types for Previous: Point on Rational Circle   Contents   Index