CGAL::Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>

Definition

The class Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits> is a model of the ArrangementTraits_2 concept and can be used to construct and maintain arrangements of bounded segments of algebraic curves of degree $$2 at most, also known as conic curves.

A general conic curve $$C is the locus of all points $$(x,y) satisfying the equation: $$r x² + s y² + t x y + u x + v y + w = 0, where:

• If $$4 r s - t² > 0, $$C is an ellipse. A special case occurs when $$r = s and $$t = 0, when $$C becomes a circle.
• If $$4 r s - t² < 0, $$C is a hyperbola.
• If $$4 r s - t² = 0, $$C is a parabola. A degenerate case occurs when $$r = s = t = 0, when $$C is a line.

A bounded conic arc is defined as either of the following:

• A full ellipse (or a circle) $$C.
• The tuple $$ C, p_s, p_t, o , where $$C is the supporting conic curve, with the arc endpoints being $$p_s and $$p_t (the source and target points, respectively). The orientation $$o indicates whether we proceed from $$p_s to $$p_t in a clockwise or in a counterclockwise direction. Note that $$C may also correspond to a line or to pair of lines - in this case $$o may specify a COLLINEAR orientation.

A very useful subset of the set of conic arcs are line segments and circular arcs, as arrangements of circular arcs and line segments have some interesting applications (e.g. offsetting polygons, motion planning for a disc robot, etc.). Circular arcs and line segment are simpler objects and can be dealt with more efficiently than arbitrary arcs. For these reasons, it is possible to construct conic arcs from segments and from circles. Using these constructors is highly recommended: It is more straightforward and also speeds up the arrangement construction. However, in case the set of input curves contain only circular arcs and line segments, it is recommended to use the Arr_circle_segment_2 class to achieve faster running times.

In our representation, all conic coefficients (namely $$r, s, t, u, v, w) must be rational numbers. This guarantees that the coordinates of all arrangement vertices (in particular, those representing instersection points) are algebraic numbers of degree $$4 (a real number $$ is an algebraic number of degree $$d if there exist a polynomial $$p with integer coefficient of degree $$d such that $$p() = 0). We therefore require separate representations of the curve coefficients and the point coordiantes. The NtTraits should be instantiated with a class that defines nested Integer, Rational and Algebraic number types and supports various operations on them, yielding certified computation results (for example, it can convert rational numbers to algebraic numbers and can compute roots of polynomials with integer coefficients). The other template parameters, RatKernel and AlgKernel should be geometric kernels templated with the NtTraits::Rational and NtTraits::Algebraic number types, repectively. It is recommended to instantiate the CORE_algebraic_number_traits class as the NtTraits parameter, with Cartesian<NtTraits::Rational> and Cartesian<NtTraits::Algebraic> instantiating the two kernel types, respectively. The number types in this case are provided by the CORE library, with its ability to exactly represent simple algebraic numbers.

The traits class inherits its point type from AlgKernel::Point_2, and defines a curve and $$x-monotone curve types, as detailed below.

#include <CGAL/Arr_conic_traits_2.h>

Is Model for the Concepts

Class Arr_conic_traits_2$$<RatKernel,AlgKernel,NtTraits$$>::Curve_2

The Curve_2 class nested within the conic-arc traits can represent arbitrary conic arcs and support their construction in various ways. The copy and default constructor as well as the assignment and equality operators are provided for conic arcs. In addition, an operator<< for the curves is defined for standard output streams.

Types

Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2::Rational
	the NtTraits::Rational type (and also the RatKernel::FT type).
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2::Algebraic
	the NtTraits::Algebraic type (and also the AlgKernel::FT type).

Creation

Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( typename RatKernel::Segment_2 seg);
	constructs an arc corresponding to the line segment seg.
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( typename RatKernel::Circle_2 circ);
	constructs an arc corresponding to the full circle circ (note that this circle has a center point with rational coordinates and rational squared radius).
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( typename RatKernel::Circle_2 circ, Orientation o, Point_2 ps, Point_2 pt);
	constructs a circular arc supported by the circle circ, going in the given orientation o from the source point ps to its target point pt. Precondition: ps and pt both lie on the circle circ. Precondition: o is not COLLINEAR.
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( typename RatKernel::Point_2 p1, typename RatKernel::Point_2 p2, typename RatKernel::Point_2 p3);
	constructs a circular arc going from p1 (its source point) through p2 to p3 (its target point). Note that all three points have rational coordinates. The orientation of the arc is determined automatically. Precondition: The three points are not collinear.
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( Rational r, Rational s, Rational t, Rational u, Rational v, Rational w);
	constructs a conic arc that corresponds to the full conic curve $$r x2 + s y2 + t x y + u x + v y + w = 0. Precondition: As a conic arc must be bounded, the given curve must be an ellipse, that is $$4 r s - t2 > 0.
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( Rational r, Rational s, Rational t, Rational u, Rational v, Rational w, Orientation o, Point_2 ps, Point_2 pt);
	constructs a conic arc supported by the conic curve $$r x2 + s y2 + t x y + u x + v y + w = 0, going in the given orientation o from the source point ps to its target point pt. Precondition: ps and pt both satisfy the equation of the supporting conic curve and define a bounded segment of this curve (e.g. in case of a hyperbolic arc, both point should be located on the same branch of the hyperbola). Precondition: o is not COLLINEAR if the supporting conic is curves, and must be COLLINEAR if it is not curved (a line or a line-pair).
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( typename RatKernel::Point_2 p1, typename RatKernel::Point_2 p2, typename RatKernel::Point_2 p3, typename RatKernel::Point_2 p4, typename RatKernel::Point_2 p5);
	constructs a conic arc going from p1 (its source point) through p2, p3 and p4 (in this order) to p5 (its target point). Note that all five points have rational coordinates. The orientation of the arc is determined automatically. Precondition: No three points of the five are not collinear. Precondition: The five points define a valid arc, in their given order.
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2 a ( Rational r, Rational s, Rational t, Rational u, Rational v, Rational w, Orientation o, Point_2 app_ps, Rational r1, Rational s1, Rational t1, Rational u1, Rational v1, Rational w1, Point_2 app_pt, Rational r2, Rational s2, Rational t2, Rational u2, Rational v2, Rational w2);
	constructs a conic arc supported by the conic curve $$r x2 + s y2 + t x y + u x + v y + w = 0, going in the given orientation o from its source point to its target point. In this case only some approximations of the endpoints (app_ps and app_pt, repsectively) is available, and their exact locations are given implicitly, specified by the intersections of the supporting conic curve with $$r1 x2 + s1 y2 + t1 x y + u1 x + v1 y + w1 = 0 and $$r2 x2 + s2 y2 + t2 x y + u2 x + v2 y + w2 = 0, repsectively. Precondition: The two auxiliary curves specifying the endpoints really intersect with the supporting conic curve, such that the arc endpoints define a bounded segment of the supporting curve (e.g. in case of a hyperbolic arc, both point should be located on the same branch of the hyperbola). Precondition: o is not COLLINEAR if the supporting conic is curves, and must be COLLINEAR if it is not curved (a line or a line-pair).

Access Functions

bool	a.is_valid ()	indicates whether a is a valid conic arc. As the precondition to some of the constructor listed above are quite complicated, their violation does not cause the program to abort. Instead, the constructed arc is invalid (a defaultly constructed arc is also invalid). It is however recommended to check that a constructed arc is valid before inserting it to an arrangement, as this operation will cause the program to abort.
bool	a.is_x_monotone ()	determines whether the arc is $$x-monotone, namely each vertical line intersects it at most once. A vertical line segment is also considered (weakly) $$x-monotone.
bool	a.is_y_monotone ()	determines whether the arc is $$y-monotone, namely each horizontal line intersects it at most once. A horizontal line segment is also considered (weakly) $$x-monotone.
bool	a.is_full_conic ()	indicates whether the arc represents a full conic curve (en ellipse or a circle).

The six following methods return the coefficients of the supported conic, after their conversion to integer number (reprsented by the Integer type of the NtTraits class):

typename NtTraits::Integer
	a.r ()	returns the coefficient of $$x2.
typename NtTraits::Integer
	a.s ()	returns the coefficient of $$t2.
typename NtTraits::Integer
	a.t ()	returns the coefficient of $$x y.
typename NtTraits::Integer
	a.u ()	returns the coefficient of $$x.
typename NtTraits::Integer
	a.v ()	returns the coefficient of $$y.
typename NtTraits::Integer
	a.w ()	returns the free coefficient.
Point_2	a.source ()	returns the source point of the arc. Precondition: a is not a full conic curve.
Point_2	a.target ()	returns the target point of the arc. Precondition: a is not a full conic curve.
Orientation	a.orientation ()	returns the orientation of the arc.
Bbox_2	a.bbox ()	return a bounding box of the arc a.

Operations

void	a.set_source ( Point_2 ps)
		sets a new source point for the conic arc. Precondition: ps lies on the supporting conic of a.
void	a.set_target ( Point_2 pt)
		sets a new target point for the conic arc. Precondition: pt lies on the supporting conic of a.

Class Arr_conic_traits_2$$<RatKernel,AlgKernel,NtTraits$$>::X_monotone_curve_2

The X_monotone_curve_2 class nested within the conic-arc traits is used to represent $$x-monotone conic arcs. It inherits from the Curve_2 type, therefore supports the access methods and the operations listed above.

For efficiency reasons, we recommend users not to construct $$x-monotone conic arc directly, but rather use the Make_x_monotone_2 functor supplied by the conic-arc traits class to convert conic curves to $$x-monotone curves.

Creation

Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>:: X_monotone_curve_2 xa ( Curve_2 arc);
	converts the given arc to an $$x-monotone arc. Precondition: arc is $$x-monotone.

Access Functions

Point_2	xa.left ()	returns the left (lexicographically smaller) endpoint of xa.
Point_2	xa.right ()	returns the right (lexicographically larger) endpoint of xa.