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< r_circle_point> | cs.intersection(const rat_line& l) | |
computes cs l (ordered along l ). | ||
list< real_point> | cs.intersection(const real_line& l) | |
as above. | ||
list< r_circle_point> | cs.intersection(const rat_circle& c) | |
computes cs c (ordered lexicographically). | ||
list< r_circle_point> | 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< point> | 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< rat_point> | cs.approximate_by_rat_points(double dist) | |
as above, returns rat_points instead of points. | ||
list< rat_segment> | 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< r_circle_segment> & L, GRAPH< r_circle_point,r_circle_segment> & 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) . |