CGAL::Arr_rational_arc_traits_2<AlgKernel,NtTraits>

Definition

The traits class Arr_rational_arc_traits_2<AlgKernel,NtTraits> is a model of the ArrangementTraits_2 concept. It handles bounded segments of rational functions, referred to as rational arcs, and enables the construction and maintenance of arrangements of such arcs. A rational function $$y = (P(x))/(Q(x)) is defined by two polynomials $$P and $$Q of arbitrary degrees. In particular, if $$Q(x) = 1 then the function is a simple polynomial function. A bounded rational arc is defined by the graph of a rational function over some internal $$[x_min, x_max], where $$Q does not have any real roots in this interval (thus the arc does not contain any poles). Rational functions, and polynomial functions in particular, are not only interesting in their own right, they are also very useful for approximating or interpolating more complicated curves.

In our representation, all polynomial coefficients (the coefficients of $$P and $$Q) must be rational numbers. This guarantees that the $$x-coordinates of all arrangement vertices (in particular, those representing instersection points) can be represneted as roots of polynomials with integer coefficients - namely, algebraic numbers. The $$y-coordinates can be obtained by simple arithmetic operations on the $$x-coordinates, hence they are also algebraic numbers.

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, in can convert rational numbers to algebraic numbers and can compute roots of polynomials with integer coefficients). The AlgKernel template-parameter should be a geometric kernel templated with the NtTraits::Algebraic number-type. It is recommended to instantiate the CORE_algebraic_number_traits class as the NtTraits parameter, with Cartesian<NtTraits::Algebraic> instantiating the kernel. The number types in this case are provided by the CORE library, with its ability to exactly represent simple algebraic numbers.

The traits class defined its point type to be AlgKernel::Point_2, and defines a curve type (and an identical $$x-monotone curve type, as a rational arc is always $$x-monotone by definition) as detailed below.

#include <CGAL/Arr_rational_arc_traits_2.h>

Is Model for the Concepts

Class Arr_rational_arc_traits_2$$<AlgKernel,NtTraits$$>::Curve_2

The Curve_2 class nested within the rational-arc traits is used to represent rational arcs and support their construction from a single polynomial and the range where the arc is defined or a pair of polynomials and a pair of corresponding ranges. The copy and default constructor as well as the assignment operator are provided for polyline curves. In addition, an operator<< for the curves is defined for standard output streams.

Types

Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2::Rat_vector
	A vector of rational numbers (equivalent to std::vector<typename NtTraits::Rational).
Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2::Polynomial
	the NtTraits::Polynomial type (a polynomial with integer coefficients).

Creation

Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2 a;
	default constructor.
Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2 a ( Rat_vector p_coeffs, typename NtTraits::Algebraic s_x, typename NtTraits::Algebraic t_x);
	constructs an arc supported by the polynomial $$y = P(x), defined over the interval [x_s, x_t], given by the $$x-coordinates of the arc's source and target. The vector p_coeffs specifies the coefficients of $$P(x), where the polynomial degree is p_coeffs.size() - 1 and p[k] is the coefficient of $$xk in $$P. Precondition: s_x != t_x.
Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2 a ( Rat_vector p_coeffs, Rat_vector q_coeffs, typename NtTraits::Algebraic s_x, typename NtTraits::Algebraic t_x);
	constructs an arc supported by the rational function $$y = (P(x))/(Q(x)), defined over the internal [s_x, t_x], given by the $$x-coordinates of the arc's source and target. The vectors p_coeffs and q_coeffs specify the coefficients of $$P(x) and $$Q(x), respectively (see above). Precondition: x_min < x_max. Precondition: For each x_min $$ x $$ x_max, $$Q(x) 0.

Access Functions

bool	a.is_valid ()	indicates whether a is a valid rational arc. As the precondition $$Q(x) 0 to the constructor from two polynomials is quite complicated, its 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.
Polynomial	a.numerator ()	returns a polynomial with integer coefficients equivalent to $$P(x).
Polynomial	a.denominator ()	returns a polynomial with integer coefficients equivalent to $$Q(x).
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.
Point_2	a.left ()	returns the left (lexicographically smaller) endpoint of a.
Point_2	a.right ()	returns the right (lexicographically larger) endpoint of a.