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 or unbounded segments of rational functions, referred to as rational arcs (in particaular, a rational arc may correspond to the entire graph of a rational function), and enables the construction and maintenance of arrangements of such arcs. 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.

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 [xmin, xmax], where Q does not have any real roots in this interval (thus the arc does not contain any poles). However, our traits class is also capable of representing functions defined over an unbounded x-range, namely a ``ray'' defined on (- , xmax] or on [xmin, ), or an entire function defined for all real x values. Note that a rational arc is unbounded even if it is defined over some bounded interval, yet Q has zeros in this interval.

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

ArrangementTraits_2

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 an x-definition range or from a pair of polynomials and an x-definition range. The copy and default constructor as well as the assignment operator are provided for rational arcs. In addition, an operator<< for the arcs 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);
constructs an arc that corresponds to the polynomial y = P(x), defined for every real x. 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.


Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2 a ( Rat_vector p_coeffs, typename NtTraits::Algebraic s_x, bool dir_right);
constructs an arc supported by the polynomial y = P(x). If dir_right is true, the arc is defined over the interval [sx, ), otherwise it is defined over (- , sx]. The vector p_coeffs specifies the coefficients of P(x) as above.
Precondition: s_x != t_x.


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 [sx, tx], given by the x-coordinates of the arc's source and target. The vector p_coeffs specifies the coefficients of P(x) as above.
Precondition: s_x != t_x.


Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2 a ( Rat_vector p_coeffs, Rat_vector q_coeffs);
constructs an arc supported by the rational function y = (P(x))/(Q(x)), defined for every real x. The vectors p_coeffs and q_coeffs specify the coefficients of P(x) and Q(x), respectively (see above).


Arr_rational_arc_traits_2<AlgKernel,NtTraits>::Curve_2 a ( Rat_vector p_coeffs,
Rat_vector q_coeffs,
typename NtTraits::Algebraic s_x,
bool dir_right);
constructs an arc supported by the rational function y = (P(x))/(Q(x)). If dir_right is true, the arc is defined over the interval [sx, ), otherwise it is defined over (- , sx]. The vectors p_coeffs and q_coeffs specify the coefficients of P(x) and Q(x), respectively (see above).


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 [sx, tx], 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: s_x != t_x.

Access Functions

bool a.is_continuous () returns whether a is continuous, namely whether it does not conatains any poles in its interior. x-monotone curves are always continuous.

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

Boundary_type a.source_boundary_in_x () returns whether the x-coordinate of the source is finite or whether it is ± .
Boundary_type a.source_boundary_in_y () returns whether the y-coordinate of the source is finite or whether it is ± .
Point_2 a.source () returns the source point of the arc.
Precondition: The source is finite in both x and y.
typename NtTraits::Algebraic a.source_x () Get the x-coordinate of the source point.
Precondition: The source point is finite in x.
typename NtTraits::Algebraic a.source_y () Get the y-coordinate of the source point.
Precondition: The source point is finite in y.

Boundary_type a.target_boundary_in_x () returns whether the x-coordinate of the target is finite or whether it is ± .
Boundary_type a.target_boundary_in_y () returns whether the y-coordinate of the target is finite or whether it is ± .
Point_2 a.target () returns the target point of the arc.
Precondition: The target is finite in both x and y.
typename NtTraits::Algebraic a.target_x () Get the x-coordinate of the target point.
Precondition: The target point is finite in x.
typename NtTraits::Algebraic a.target_y () Get the y-coordinate of the target point.
Precondition: The target point is finite in y.

Boundary_type a.left_boundary_in_x () returns whether the x-coordinate of a's left end is finite or whether it is ± .
Boundary_type a.left_boundary_in_y () returns whether the y-coordinate of a's left end is finite or whether it is ± .
Point_2 a.left () returns the left (lexicographically smaller) endpoint of a.
Precondition: The left end is finite in both x and y.

Boundary_type a.right_boundary_in_x () returns whether the x-coordinate of a's right end is finite or whether it is ± .
Boundary_type a.right_boundary_in_y () returns whether the y-coordinate of a's right end is finite or whether it is ± .
Point_2 a.right () returns the right (lexicographically larger) endpoint of a.
Precondition: The right end is finite in both x and y.