Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL

CGAL::Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits>

Definition

The traits class Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits> is a model of the ArrangementTraits_2 concept that handles planar Bézier curves. A planar Bézier curve B is a parametric curve defined by a sequence of control points p0, … , pn as follows:

B(t) = (X(t), Y(t)) =
n
∑
k=0
pk ⋅
n!
k! (n-k)!
 ⋅ tk (1-t)n-k
 .
where t ∈ [0, 1]. The degree of the curve is therefore n - namely, X(t) and Y(t) are polynomials of degree n. Bézier curves have numerous applications in computer graphics and solid modelling. They are used, for example, in free-form sketches and for defining the true-type fonts.

In our representation, we assume that the coordinates of all control points are rational numbers (namely they are given as objects of the RatKernel::Point_2 type), so both X(t) and Y(t) are polynomials with rational coefficients. The intersection points between curves are however algebraic numbers, and their exact computation is time-consuming. The traits class therefore contains a layer of geometric filtering that performs all computation in an approximate manner whenever possible, and it resorts to exact computations only when the approximate computation fails to produce an unambiguous result.

We therefore require separate representations of the control points and the intersection points. 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 other template parameters, RatKernel and AlgKernel should be geometric kernels templated with the NtTraits::Rational and NtTraits::Algebraic number types, respectively. 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.

#include <CGAL/Arr_Bezier_curve_traits_2.h>

Is Model for the Concepts

ArrangementTraits_2

Types

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


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

Class Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits>::Curve_2

The Curve_2 class nested within the Bézier traits class is used to represent a Bézier curve of arbitrary degree, which is defined by a sequence of rational control points. In addition to the methods listed below, the I/O operators operator<< and operator>> for standard output-streams are also supported. The copy constructor and assignment operator are supported as well.

Creation

Arr_Bezier_curve_traits_2<AlgKernel,NtTraits>::Curve_2 B;
default constructor.


template <class InputIterator>
Arr_Bezier_curve_traits_2<AlgKernel,NtTraits>::Curve_2 B ( InputIterator pts_begin, InputIterator pts_end);
constructs a Bézier curve as defined by the given range of control points. The value-type of InputIterator is RatKernel::Point_2.
Precondition: The input range must contain at least two control points.

Access Functions

size_t B.number_of_control_point () const
returns the number of control points that define B.

typename RatKernel::Point_2 B.control_point ( size_t k) const returns the kth control point. Note that the first control point equals the curve source, while the last control point equals its target. The rest of the control points do not lie on the curve.
Precondition: k is smaller than the number of control points.

typename RatKernel::Point_2 B ( Rational t ) const returns the point B(t) on the curve that corresponds to the given rational parameter value.

typename AlgKernel::Point_2 B ( Algebraic t ) const returns the point B(t) on the curve that corresponds to the given algebraic parameter value.

Class Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits>::Point_2

The Point_2 class nested within the Bézier traits class is used to represent: (i) an endpoint of a Bézier curve, (ii) a vertical tangency point of a curve, used to subdivide it into x-monotone subcurve, and (iii) an intersection point between two curves. While, points of type (i) have rational coordinates and are given as part of the input, points of the two latter types have algebraic coordinates. However, to speed up the arrangement construction, such point are not computed in an exact manner, and instead are given in an approximate representation. Note that the exact coordinates of a point may only be accessed if it is exactly computed.

In addition to the methods listed below, the copy constructor and assignment operator for Point_2 objects are also supported.

Creation

Arr_Bezier_curve_traits_2<AlgKernel,NtTraits>::Point_2 p;
default constructor.


Arr_Bezier_curve_traits_2<AlgKernel,NtTraits>::Point_2 p ( Curve_2 B, Algebraic t_0);
constructs the point B(t0) on the given curve. As t0 is an algebraic number, the point has algebraic coordinates.


Arr_Bezier_curve_traits_2<AlgKernel,NtTraits>::Point_2 p ( Curve_2 B, Rational t_0);
constructs the point B(t0) on the given curve. As t0 is a rational number, the point has rational coordinates.

Access Functions

std::pair<double, double> p.approximate () const returns the approximated coordinates of p.

bool p.is_exact () const returns whether the coordinates of p are computed in an exact manner.

Algebraic p.x () const returns the x-coordinate of p.
Precondition: p is exactly computed.
Algebraic p.y () const returns the y-coordinate of p.
Precondition: p is exactly computed.

bool p.is_rational () const returns whether the coordinates of p are rational numbers.

typename RatKernel::Point_2 typename RatKernel::Point_2 ( p) const
casts p to a point with rational coordinates.
Precondition: p has rational coordinates.

Class Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits>::X_monotone_curve_2

The X_monotone_curve_2 class nested within the Bézier traits is used to represent x-monotone subcurves of Bézier curves. The subcurve is defined by a supporting Bézier curve B(t) and a range of definition in the parameter space [t1, t2] ⊆ [0, 1], where B(t1) is the subcurve source and B(t2) is its target. Note that as the point endpoints may only be approximated, the parameter range defining the subcurve may only be approximately known.

It is not possible to construct x-monotone subcurves directly. Instead, use the Make_x_monotone_2 functor supplied by the traits class to subdivide a Curve_2 object into x-monotone subcurves.

Access Functions

Curve_2 b.supporting_curve () const returns the supporting Bézier curve of b.

Point_2 b.source () const returns the source point of b.
Point_2 b.target () const returns the target point of b.

Point_2 b.left () const returns the left (xy-lexicographically smaller) endpoint of b.
Point_2 b.right () const returns the right (xy-lexicographically smaller) endpoint of b.

std::pair<double, double> b.parameter_range () const return the approximate parameter range defining the subcurve b.

Next: Arr_algebraic_segment_traits_2<Coefficient>
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 3.9. 26 September 2011.