Definition
An instance of data type rat_vector is a vector of rational numbers. A d-dimensional vector r = (r_{0},..., r_{d-1}) is represented in homogeneous coordinates (h_{0},..., h_{d}), where r_{i} = h_{i}/h_{d} and the h_{i}'s are of type integer. We call the r_{i}'s the cartesian coordinates of the vector. The homogenizing coordinate h_{d} is positive.
This data type is meant for use in computational geometry. It realizes free vectors as opposed to position vectors (type rat_point). The main difference between position vectors and free vectors is their behavior under affine transformations, e.g., free vectors are invariant under translations.
rat_vector is an item type.
#include < LEDA/numbers/rat_vector.h >
Creation
rat_vector | v(int d=2) | introduces a variable v of type rat_vector initialized to the zero vector of dimension d. |
rat_vector | v(integer a, integer b, integer D) | |
introduces a variable v of type rat_vector
initialized to the two-dimensional vector with homogeneous
representation (a, b, D) if D is positive and representation
(- a, - b, - D) if D is negative.
Precondition D is non-zero. |
||
rat_vector | v(rational x, rational y) | introduces a variable v of type rat_vector initialized to the two-dimensional vector with homogeneous representation (a, b, D), where x = a/D and y = b/D. |
rat_vector | v(integer a, integer b, integer c, integer D) | |
introduces a variable v of type rat_vector
initialized to the three-dimensional vector with homogeneous
representation (a, b, c, D) if D is positive and representation
(- a, - b, - c, - D) if D is negative.
Precondition D is non-zero. |
||
rat_vector | v(rational x, rational y, rational z) | |
introduces a variable v of type rat_vector initialized to the three-dimensional vector with homogeneous representation (a, b, c, D), where x = a/D, y = b/D and z = c/D. | ||
rat_vector | v(const array<rational>& A) | |
introduces a variable v of type rat_vector initialized to the d-dimensional vector with homogeneous coordinates (c_{0},...,c_{d-1},D), where d = A.size() and A[i] = c_{i}/D, for i = 0,..., d - 1. | ||
rat_vector | v(integer a, integer b) | introduces a variable v of type rat_vector initialized to the two-dimensional vector with homogeneous representation (a, b, 1). |
rat_vector | v(const integer_vector& c, integer D) | |
introduces a variable v of type rat_vector
initialized to the vector with homogeneous
coordinates
(c_{0},...,c_{d-1},D),
where d is the dimension of c and the sign
chosen is the sign of D.
Precondition D is non-zero. |
||
rat_vector | v(const integer_vector& c) | |
introduces a variable v of type rat_vector
initialized to the direction with homogeneous coordinate
vector c, where the sign chosen is the sign of the
last component of c. Precondition The last component of c is non-zero. |
||
rat_vector | v(const vector& w, int prec) | |
introduces a variable v of type rat_vector initialized to (P*w_{0},...,P*w_{d-1}, P), where d is the dimension of w and P = 2^{prec}. |
Operations
3.1 Initialization, Access and Conversions
rat_vector | rat_vector::d2(integer a, integer b, integer D) | |
returns a rat_vector of dimension 2 initialized to a
vector with homogeneous representation (a, b, D) if D
is positive and representation
(- a, - b, - D) if D is
negative.
Precondition D is non-zero. |
||
rat_vector | rat_vector::d3(integer a, integer b, integer c, integer D) | |
returns a rat_vector of dimension 3 initialized to a
vector with homogeneous representation (a, b, c, D) if D
is positive and representation
(- a, - b, - c, - D) if D is
negative.
Precondition D is non-zero. |
||
rat_vector | rat_vector::unit(int i, int d=2) | |
returns a rat_vector of dimension d initialized
to the i-th unit vector.
Precondition 0 < = i < d. |
||
rat_vector | rat_vector::zero(int d=2) | returns the zero vector in d-dimensional space. |
int | v.dim() | returns the dimension of v. |
integer | v.hcoord(int i) | returns the i-th homogeneous coordinate of v. |
rational | v.coord(int i) | returns the i-th cartesian coordinate of v. |
rational | v[int i] | returns the i-th cartesian coordinate of v. |
rational | v.sqr_length() | returns the square of the length of v. |
vector | v.to_float() | returns a floating point approximation of v. |
Additional Operations for vectors in two and three-dimensional space
rational | v.xcoord() | returns the zero-th cartesian coordinate of v. |
rational | v.ycoord() | returns the first cartesian coordinate of v. |
rational | v.zcoord() | returns the second cartesian coordinate of v. |
integer | v.X() | returns the zero-th homogeneous coordinate of v. |
integer | v.Y() | returns the first homogeneous coordinate of v. |
integer | v.Z() | returns the second homogeneous coordinate of v. |
integer | v.W() | returns the homogenizing coordinate of v. |
rat_vector | v.rotate90(int i=1) | returns v by an angle of i x 90 degrees. If i > 0 the rotation is counter-clockwise otherwise it is clockwise. Precondition v.dim() == 2. |
int | compare_by_angle(const rat_vector& v1, const rat_vector& v2) | |
For a non-zero vector v let (v) be the angle by which the positive x-axis has to be turned counter-clockwise until it aligns with v. The function compares the angles defined by v1 and v2, respectively. The zero-vector precedes all non-zero vectors in the angle-order. | ||
rat_vector | cross_product(const rat_vector& v1, const rat_vector& v2) | |
returns the cross product of the three-dimensional vectors v1 and v2. |
3.2 Tests
bool | v == const rat_vector& w | Test for equality. |
bool | v != const rat_vector& w | Test for inequality. |
3.3 Arithmetical Operators
rat_vector | integer n * const rat_vector& v | |
multiplies all cartesian coordinates by n. | ||
rat_vector | rational r * const rat_vector& v | |
multiplies all cartesian coordinates by r. | ||
rat_vector& | v *= integer n | multiplies all cartesian coordinates by n. |
rat_vector& | v *= rational r | multiplies all cartesian coordinates by r. |
rat_vector | const rat_vector& v / integer n | |
divides all cartesian coordinates by n. | ||
rat_vector | const rat_vector& v / rational r | |
divides all cartesian coordinates by r. | ||
rat_vector& | v /= integer n | divides all cartesian coordinates by n. |
rat_vector& | v /= rational r | divides all cartesian coordinates by r. |
rational | const v * const rat_vector& w | |
scalar product, i.e., v_{i}w_{i}, where v_{i} and w_{i} are the cartesian coordinates of v and w respectively. | ||
rat_vector | const rat_vector& v + const rat_vector& w | |
adds cartesian coordinates. | ||
rat_vector& | v += const rat_vector& w | addition plus assignment. |
rat_vector | const rat_vector& v - const rat_vector& w | |
subtracts cartesian coordinates. | ||
rat_vector& | v -= const rat_vector& w | subtraction plus assignment. |
rat_vector | -v | returns -v. |
3.4 Input and Output
ostream& | ostream& O « const rat_vector& v | |
writes v's homogeneous coordinates componentwise to the output stream O. | ||
istream& | istream& I » rat_vector& v | |
reads v's homogeneous coordinates componentwise from the input stream I. The operator uses the current dimension of v. |
3.5 Linear Hull, Dependence and Rank
bool | contained_in_linear_hull(const array<rat_vector>& A, const rat_vector& x) | |
determines whether x is contained in the linear hull of the vectors in A. | ||
int | linear_rank(const array<rat_vector>& A) | |
computes the linear rank of the vectors in A. | ||
bool | linearly_independent(const array<rat_vector>& A) | |
decides whether the vectors in A are linearly independent. | ||
array<rat_vector> | linear_base(const array<rat_vector>& A) | |
computes a basis of the linear space spanned by the vectors in A. |
Implementation
Vectors are implemented by arrays of integers as an item type. All operations like creation, initialization, tests, vector arithmetic, input and output on an vector v take time O(v.dim()). dim(), coordinate access and conversions take constant time. The operations for linear hull, rank and independence have the cubic costs of the used matrix operations. The space requirement is O(v.dim()).