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/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 two-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 two-dimensional vector with homogeneous representation (a, b, c, D), where x = a/D, y = b/D and z = c/D. | ||
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(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(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(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() | returns the v rotated by 90 degrees.
Precondition v.dim() == 2. |
int | compare_by_angle(rat_vector v1, 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. |
3.2 Tests
bool | v == w | Test for equality. |
bool | v != w | Test for inequality. |
3.3 Arithmetical Operators
rat_vector | integer n * v | multiplies all cartesian coordinates by n. |
rat_vector | rational r * 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 | v / integer n | divides all cartesian coordinates by n. |
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 * 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 | v + w | adds cartesian coordinates. |
rat_vector& | v += w | addition plus assignment. |
rat_vector | v - w | subtracts cartesian coordinates. |
rat_vector& | v -= w | subtraction plus assignment. |
rat_vector | -v | returns -v. |
3.4 Input and Output
ostream& | ostream& O << 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(array<rat_vector> A, rat_vector x) | |
determines whether x is contained in the linear hull of the vectors in A. | ||
int | linear_rank(array<rat_vector> A) | |
computes the linear rank of the vectors in A. | ||
bool | linearly_independent(array<rat_vector> A) | |
decides whether the vectors in A are linearly independent. | ||
array<rat_vector> | linear_base(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()).