Rational Vectors ( rat_vector )

Definition

An instance of data type rat_vector is a vector of rational numbers. A d-dimensional vector r = (r₀,..., r_{d - 1}) is represented in homogeneous coordinates (h₀,..., 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 (+ - c0,..., + - cd - 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 ($\lfloor$P*w0$\rfloor$,...,$\lfloor$P*wd - 1$\rfloor$, P), where d is the dimension of w and P = 2prec.

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_vector()	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  alpha (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., $\sum_{0 <= i < d}^{}$viwi, where vi and wi 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()).