CGAL::Arr_rational_function_traits_2<AlgebraicKernel_d_1>

Definition

The traits class Arr_rational_function_traits_2<AlgebraicKernel_d_1> is a model of the ArrangementTraits_2 concept. It handles bounded and unbounded arcs of rational functions, referred to as rational arcs (in particular, such an arc may correspond to the entire graph of a rational function), 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. If Q(x) = 1 then the function is a simple polynomial function. Usually the domain is but the function may also be restricted to a bounded interval [xmin, xmax] or defined over a ray (-∞, xmax] or over [xmin, ∞). Rational functions are represented by the nested type Curve_2. Note that a rational function may be not continuous since roots of Q induce vertical asymptotes, which would contradict the notion of an x-monotone curve as it is introduced by the ArrangementTraits_2 concept. Thus, continuous portions of rational functions are represented by the nested type X_monotone_curve_2, which is different from Curve_2. Constructors for both classes are provided by the traits. A Curve_2 may be split up into several X_monotone_curve_2 using Make_x_monotone_2.

The template parameter of the traits must be a model of the concept AlgebraicKernel_d_1. A rational function is then represented by two polynomials P and Q of type AlgebraicKernel_d_1::Polynomial_1. A point is represented by a rational function and its x-coordinate, which is of type AlgebraicKernel_d_1::Algebraic_real_1. Note that an explicit representation of the y-coordinate is only computed upon request, which can be a rather costly operation.

The constructed rational functions are cached by the traits class. The cache is local to each traits class object. It is therefore necessary to construct the curves using the constructor objects provided by member functions of the traits class. Moreover, a curve must only be used with its own traits. The cache is automatically cleaned up from time to time. The amortized clean up costs are constant. However, there is also a separate member function that cleans up the cache on demand.

#include <CGAL/Arr_rational_function_traits_2.h>

Is Model for the Concepts

ArrangementTraits_2
ArrangementDirectionalXMonotoneTraits_2
ArrangementOpenBoundaryTraits_2

Types

typedef AlgebraicKernel_d_1 Algebraic_kernel_d_1;
typedef AlgebraicKernel_d_1::Coefficient
Coefficient;
typedef AlgebraicKernel_d_1::Polynomial_1
Polynomial_1;
typedef AlgebraicKernel_d_1::Algebraic_real_1
Algebraic_real_1;
typedef AlgebraicKernel_d_1::Bound
Bound;

Creation

Arr_rational_function_traits_2<AlgebraicKernel_d_1> traits ( const Algebraic_kernel_d_1* kernel);
constructs an empty traits that uses the kernel pointed by kernel for performing algebraic operations.

Operations

Construct_curve_2 traits.construct_curve_2_object () const
Returns an instance of Construct_curve_2.
Construct_x_monotone_curve_2 traits.construct_x_monotone_curve_2_object () const
Returns an instance of Construct_x_monotone_curve_2.
void traits.cleanup_cache () const Deletes all curves from the cache that exist only there.

const Algebraic_kernel_d_1* traits.algebraic_kernel_d_1 () const
Returns a pointer to the used algerbaic kernel object.

Class Arr_rational_function_traits_2<AlgebraicKernel_d_1>::Curve_2

The Curve_2 class nested within the traits is used to represent rational functions which may be restricted to a certain x-range.

Is Model for the Concepts

ArrTraits::Curve_2

Types

typedef AlgebraicKernel_d_1::Polynomial_1
Polynomial_1;
typedef AlgebraicKernel_d_1::Algebraic_real_1
Algebraic_real_1;

Operations

Polynomial_1 curve.numerator () const returns the numerator of the supporting rational function.

Polynomial_1 curve.denominator () const returns the denominator of the supporting rational function.

bool curve.is_continuous () const returns whether curve is continuous, namely whether it does not contains any vertical asymptotes in its interior.

Arr_parameter_space curve.left_parameter_space_in_x () const
returns whether the x-coordinate of curve's left end is finite or whether it is ± ∞.
Arr_parameter_space curve.right_parameter_space_in_x () const
returns whether the x-coordinate of curve's right end is finite or whether it is ± ∞.
Algebraic_real_1 curve.left_x () const returns the x-coordinate of the left end.
Precondition: left_boundary_in_x()==ARR_INTERIOR
Algebraic_real_1 curve.right_x () const returns the x-coordinate of the right end.
Precondition: right_boundary_in_x()==ARR_INTERIOR

Class Arr_rational_function_traits_2<AlgebraicKernel_d_1>::X_monotone_curve_2

The X_monotone_curve_2 class nested within the traits is used to represent x-monotone parts of rational functions. In particular, such an x-monotone curve may not contain a vertical asymptote in its interior x-range.

Is Model for the Concepts

ArrTraits::XMonotoneCurve_2

Types

typedef AlgebraicKernel_d_1::Polynomial_1
Polynomial_1;
typedef AlgebraicKernel_d_1::Algebraic_real_1
Algebraic_real_1;
typedef Arr_rational_function_traits_2<AlgebraicKernel_d_1>::Point_2
Point_2;

Operations

Polynomial_1 xcurve.numerator () const returns the numerator of the supporting rational function.

Polynomial_1 xcurve.denominator () const returns the denominator of the supporting rational function.

Arr_parameter_space xcurve.source_parameter_space_in_x () const
returns whether the x-coordinate of the source is finite or whether it is ± ∞.
Arr_parameter_space xcurve.source_parameter_space_in_y () const
returns whether the y-coordinate of the source is finite or whether it is ± ∞.
Point_2 xcurve.source () const returns the source point of the arc.
Precondition: Both the x- and y-coordinates of the source point is finite.
Algebraic_real_1 xcurve.source_x () const returns the x-coordinate of the source point.
Precondition: The x-coordinate of the source point is finite.

Arr_parameter_space xcurve.target_parameter_space_in_x () const
returns whether the x-coordinate of the target is finite or whether it is ± ∞.
Arr_parameter_space xcurve.target_parameter_space_in_y () const
returns whether the y-coordinate of the target is finite or whether it is ± ∞.
Point_2 xcurve.target () const returns the target point of the arc.
Precondition: Both the x- and y-coordinates of the target point is finite.
Algebraic_real_1 xcurve.target_x () const returns the x-coordinate of the target point.
Precondition: The x-coordinate of the target point is finite.

Arr_parameter_space xcurve.left_parameter_space_in_x () const
returns whether the x-coordinate of the left curve end is finite or whether it is ± ∞.
Arr_parameter_space xcurve.left_parameter_space_in_y () const
returns whether the y-coordinate of the left curve end is finite or whether it is ± ∞.
Point_2 xcurve.left () const returns the left point of the arc.
Precondition: Both the x- and y-coordinates of the left point is finite.
Algebraic_real_1 xcurve.left_x () const returns the x-coordinate of the left point.
Precondition: The x-coordinate of the left point is finite.

Arr_parameter_space xcurve.right_parameter_space_in_x () const
returns whether the x-coordinate of the right curve end is finite or whether it is ± ∞.
Arr_parameter_space xcurve.right_parameter_space_in_y () const
returns whether the y-coordinate of the right curve end is finite or whether it is ± ∞.
Point_2 xcurve.right () const returns the right point of the arc.
Precondition: Both the x- and y-coordinates of The right point is finite.
Algebraic_real_1 xcurve.right_x () const returns the x-coordinate of the right point.
Precondition: The x-coordinate of the right point is finite.

bool xcurve.is_left_to_right () const returns whether the curve is oriented from left to right.

Class Arr_rational_function_traits_2<AlgebraicKernel_d_1>::Point_2

Is Model for the Concepts

ArrTraits::Point_2

Types

typedef AlgebraicKernel_d_1::Polynomial_1
Polynomial_1;
typedef AlgebraicKernel_d_1::Algebraic_real_1
Algebraic_real_1;
typedef AlgebraicKernel_d_1::Bound
Bound;

Operations

Polynomial_1 point.numerator () const returns the numerator of the supporting rational function.

Polynomial_1 point.denominator () const returns the denominator of the supporting rational function.

std::pair<double,double> point.to_double () const returns double-approximations of the x- and y-coordinates.

Algebraic_real_1 point.x () const returns the x-coordinate of the point.

Algebraic_real_1 point.y () const obtains the y-coordinates of the point. Attention: As described above, points are not stored by their y-coordinate in Algebraic_real_1 representation. In fact, this representation must be computed on demand, and might become quite costly for points defined by high-degree polynomials. Therefore, it is recommended to avoid calls to this function as much as possible.

std::pair<Bound,Bound> point.approximate_absolute_x ( int a) const
Computes a pair p approximating the x-coordinate with respect to the given absolute precision a.
Postcondition: p.first x p.second
Postcondition: p.second - p.first 2-a

std::pair<Bound,Bound> point.approximate_absolute_y ( int a) const
Computes a pair p approximating the y-coordinate with respect to the given absolute precision a.
Postcondition: p.first y p.second
Postcondition: p.second - p.first 2-a

std::pair<Bound,Bound> point.approximate_relative_x ( int r) const
Computes a pair p approximating the x-coordinate with respect to the given relative precision r.
Postcondition: p.first x p.second
Postcondition: p.second - p.first 2-r|x|

std::pair<Bound,Bound> point.approximate_relative_y ( int r) const
Computes a pair p approximating the y-coordinate with respect to the given relative precision r.
Postcondition: p.first y p.second
Postcondition: p.second - p.first 2-r|y|

Class Arr_rational_function_traits_2<AlgebraicKernel_d_1>::Construct_curve_2

Functor to construct a Curve_2. To enable caching the class is not default constructible and must be obtained via the function construct_curve_2_object(), which is a member of the traits.

Is Model for the Concepts

Assignable
CopyConstructible
AdaptableBinaryFunction
AdaptableUnaryFunction

Types

typedef AlgebraicKernel_d_1::Polynomial_1
Polynomial_1;
typedef AlgebraicKernel_d_1::Algebraic_real_1
Algebraic_real_1;
typedef Arr_rational_function_traits_2<AlgebraicKernel_d_1>::Curve_2
result_type;

typedef Polynomial_1 argument_type;
typedef Polynomial_1 first_argument_type;
typedef Polynomial_1 second_argument_type;

Operations

Curve_2 construct ( Polynomial_1 P ) const Constructs a curve representing the polynomial function y = P(x).
Curve_2 construct ( Polynomial_1 P , Algebraic_real_1 x , bool right ) const
Constructs a curve representing the polynomial function y = P(x). The function is defined over the interval [x,+∞) if right is true and (-∞,x] otherwise.
Curve_2 construct ( Polynomial_1 P , Algebraic_real_1 lower , Algebraic_real_1 upper ) const
Constructs a curve representing the polynomial function y = P(x). The function is defined over the interval [lower,upper].
Curve_2 construct ( Polynomial_1 P , Polynomial_1 Q ) const
Constructs a curve representing the rational function y = P(x)/Q(x).
Curve_2 construct ( Polynomial_1 P , Polynomial_1 Q , Algebraic_real_1 x , bool right ) const
Constructs a curve representing the rational function y = P(x)/Q(x). The function is defined over the interval I=[x,+∞) if right is true and I=(-∞,x] otherwise.
Curve_2 construct ( Polynomial_1 P , Polynomial_1 Q , Algebraic_real_1 lower , Algebraic_real_1 upper ) const
Constructs a curve representing the rational function y = P(x)/Q(x). The function is defined over the interval I=[lower,upper].

template <typename InputIterator>
Curve_2 construct ( InputIterator begin , InputIterator end ) const
Constructs a curve representing the polynomial function y = P(x), where the coefficients of P are given in the range [begin,end).
template <typename InputIterator>
Curve_2 construct ( InputIterator begin , InputIterator end , Algebraic_real_1 x , bool right ) const
Constructs a curve representing the polynomial function y = P(x), where the coefficients of P are given in the range [begin,end). The function is defined over the interval [x,+∞) if right is true and (-∞,x] otherwise.
template <typename InputIterator>
Curve_2
construct ( InputIterator begin ,
InputIterator end ,
Algebraic_real_1 lower ,
Algebraic_real_1 upper )
const
Constructs a curve representing the polynomial function y = P(x), where the coefficients of P are given in the range [begin,end). The function is defined over the interval [lower,upper].
template <typename InputIterator>
Curve_2
construct ( InputIterator begin_numer ,
InputIterator end_numer ,
InputIterator begin_denom ,
InputIterator end_denom )
const
Constructs a curve representing the rational function y = P(x)/Q(x), where the coefficients of P and Q are given in the ranges [begin_numer,end_numer) and [begin_denom,end_denom), respectively.
template <typename InputIterator>
Curve_2
construct ( InputIterator begin_numer ,
InputIterator end_numer ,
InputIterator begin_denom ,
InputIterator end_denom ,
Algebraic_real_1 x ,
bool right )
const
Constructs a curve representing the rational function y = P(x)/Q(x), where the coefficients of P and Q are given in the ranges [begin_numer,end_numer) and [begin_denom,end_denom), respectively. The function is defined over the interval I=[x,+∞) if right is true and I=(-∞,x] otherwise.
template <typename InputIterator>
Curve_2
construct ( InputIterator begin_numer ,
InputIterator end_numer ,
InputIterator begin_denom ,
InputIterator end_denom ,
Algebraic_real_1 lower ,
Algebraic_real_1 upper )
const
Constructs a curve representing the rational function y = P(x)/Q(x), where the coefficients of P and Q are given in the ranges [begin_numer,end_numer) and [begin_denom,end_denom), respectively. The function is defined over the interval I=[lower,upper].

Class Arr_rational_function_traits_2<AlgebraicKernel_d_1>::Construct_x_monotone_curve_2

Functor to construct a X_monotone_curve_2. To enable caching the class is not default constructible and must be obtained via the function construct_x_monotone_curve_2_object(), which is a member of the traits.

Is Model for the Concepts

Assignable
CopyConstructible
AdaptableBinaryFunction
AdaptableUnaryFunction

Types

typedef AlgebraicKernel_d_1::Polynomial_1
Polynomial_1;
typedef AlgebraicKernel_d_1::Algebraic_real_1
Algebraic_real_1;
typedef Arr_rational_function_traits_2<AlgebraicKernel_d_1>::X_monotone_curve_2
result_type;
typedef Polynomial_1 argument_type;
typedef Polynomial_1 first_argument_type;
typedef Polynomial_1 second_argument_type;

Operations

X_monotone_curve_2 construct ( Polynomial_1 P ) const Constructs an x-monotone curve supported by the polynomial function y = P(x).
X_monotone_curve_2 construct ( Polynomial_1 P , Algebraic_real_1 x , bool right ) const
Constructs an x-monotone curve supported by the polynomial function y = P(x). The function is defined over the interval [x,+∞) if right is true and (-∞,x] otherwise.
X_monotone_curve_2 construct ( Polynomial_1 P , Algebraic_real_1 lower , Algebraic_real_1 upper )
Constructs an x-monotone curve supported by the polynomial function y = P(x). The function is defined over the interval [lower,upper].
X_monotone_curve_2 construct ( Polynomial_1 P , Polynomial_1 Q )
Constructs an x-monotone curve supported by the rational function y = P(x)/Q(x).
Precondition: Q has no real roots.
X_monotone_curve_2 construct ( Polynomial_1 P , Polynomial_1 Q , Algebraic_real_1 x , bool right )
Constructs an x-monotone curve supported by the rational function y = P(x)/Q(x). The function is defined over the interval I=[x,+∞) if right is true and I=(-∞,x] otherwise.
Precondition: Q has no real roots in the interior of I.
X_monotone_curve_2 construct ( Polynomial_1 P , Polynomial_1 Q , Algebraic_real_1 lower , Algebraic_real_1 upper )
Constructs an x-monotone curve supported by the rational function y = P(x)/Q(x). The function is defined over the interval I=[lower,upper].
Precondition: Q has no real roots in the interior of I.

template <typename InputIterator>
X_monotone_curve_2 construct ( InputIterator begin , InputIterator end ) const
Constructs an x-monotone curve supported by the polynomial function y = P(x), where the coefficients of P are given in the range [begin,end).
template <typename InputIterator>
X_monotone_curve_2 construct ( InputIterator begin , InputIterator end , Algebraic_real_1 x , bool right ) const
Constructs an x-monotone curve supported by the polynomial function y = P(x), where the coefficients of P are given in the range [begin,end). The function is defined over the interval [x,+∞) if right is true and (-∞,x] otherwise.
template <typename InputIterator>
X_monotone_curve_2
construct ( InputIterator begin ,
InputIterator end Algebraic_real_1 lower ,
Algebraic_real_1 upper )
Constructs an x-monotone curve supported by the polynomial function y = P(x), where the coefficients of P are given in the range [begin,end). The function is defined over the interval [lower,upper].
template <typename InputIterator>
X_monotone_curve_2
construct ( InputIterator begin_numer ,
InputIterator end_numer ,
InputIterator begin_denom ,
InputIterator end_denom )
Constructs an x-monotone curve supported by the rational function y = P(x)/Q(x), where the coefficients of P and Q are given in the ranges [begin_numer,end_numer) and [begin_denom,end_denom), respectively.
Precondition: Q has no real roots.
template <typename InputIterator>
X_monotone_curve_2
construct ( InputIterator begin_numer ,
InputIterator end_numer ,
InputIterator begin_denom ,
InputIterator end_denom ,
Algebraic_real_1 x ,
bool right )
Constructs an x-monotone curve supported by the rational function y = P(x)/Q(x), where the coefficients of P and Q are given in the ranges [begin_numer,end_numer) and [begin_denom,end_denom), respectively. The function is defined over the interval I=[x,+∞) if right is true and I=(-∞,x] otherwise.
Precondition: Q has no real roots in the interior of I.
template <typename InputIterator>
X_monotone_curve_2
construct ( InputIterator begin_numer ,
InputIterator end_numer ,
InputIterator begin_denom ,
InputIterator end_denom ,
Algebraic_real_1 lower ,
Algebraic_real_1 upper )
Constructs an x-monotone curve supported by the rational function y = P(x)/Q(x), where the coefficients of P and Q are given in the ranges [begin_numer,end_numer) and [begin_denom,end_denom), respectively. The function is defined over the interval I=[lower,upper].
Precondition: Q has no real roots in the interior of I.