Vectors

Back to Mathematics

A vector is an element of a vector space.

Theory

A vector space is a 4-tuple ''(V, F, +, *)'' where

• ''F'' is a field.

• ''+ : V^2 -> V''

• ''* : F xx V -> V''

• ''(V, +)'' is an Abelian group.

• ''forall alpha in F: m_{alpha}(v) = *(alpha, v)'' is an endomorphism in ''V''.

Practice

Pastel implements the Vector class template to model vectors in ''F^n'' over ''F'', where ''F'' is an ordered field (such as real numbers or rational numbers).

```template <typename Real, int N = Dynamic>
class Vector;
```

Parametrized element types

Vector's can work with different types of elements, as made possible by the template parameter Real. Examples include float, double, and the Rational class. User-defined types can also be used, given that they model the Real concept.

If we were to model vectors as they are defined in mathematics, we should choose the concept for the element type to correspond to elements of a field. However, for a geometric library this concept is too general. For example, it contains complex numbers and finite fields. Instead, we need the field to be ordered, to be able to subdivide space in a kd-tree, for example. This restricted concept leaves us with fields such as rational numbers, algebraic numbers, and real numbers.

Dynamic and static vectors

The Vector class template divides into static and dynamic vectors based on the value of N. The static ones are those for which N is a positive integer. The dynamic ones are those for which N equals the constant Dynamic.

```// Static 2d vector.
Vector<float, 2> a;

// Dynamic vector.
Vector<float, Dynamic> b;

// Also a dynamic vector per the default parameter.
Vector<float> c;
```

A dynamic vector allocates the memory for its elements dynamically. This allows it to change size at runtime. In contrast, a static vector stores its elements directly into an object in an array whose size is known at compile time. Because of this, it's size can't be changed at runtime.

Static vectors are useful when the problem to be solved resides in a fixed low dimension, such as 2 or 3. This is usually the case in computer graphics, for example. In this case static vectors are more efficient in both memory use and performance.

However, dynamic vectors are also needed frequently, especially when solving systems of linear equations. For examples from geometry, take least squares matching of ordered point sets, or interpolation with splines.

Both kinds of vectors are important, and thus Pastel implements them under a generic framework. The same algorithms work for both kinds.

To make the notation correspond to that used in mathematics, Pastel overloads the arithmetic operators for Vector's. Here is an example computation:

```Vector<float, 2> a(1, 2);
Vector<float, 2> b(3, 4);
Vector<float, 2> c = a - (4 * (a + b - 2)) / 3;
```

Array programming

The multiplication and division operators have been extended to work with vectors in an element-wise manner:

```Vector<float, 2> a(1, 2);
Vector<float, 2> b(3, 4);
Vector<float, 2> c = (a * b) / (a + b);
Vector<float, 2> d(
(float)(1 * 3) / (1 + 3),
(float)(2 * 4) / (2 + 4));
ENSURE(allEqual(c, d));
```

The standard mathematical functions have been extended in a similar element-wise manner. These functions include the familiar sin, cos, exp, log, pow, etc. Comparison functions have been extended to vectors by the functions anyLess, allLess, anyEqual, allEqual, etc.

```Vector<float, 2> a(1, 2);
Vector<float, 2> b = 2 * sin(a) * cos(a);
Vector<float, 2> c(
2 * sin(1) * cos(1),
2 * sin(2) * cos(2));
ENSURE(allEqual(b, c));
```

If there are scalars in an expressions, they work as if they were extended to appropriately sized vectors, and the operation then carried out element-wise:

```Vector<float, 2> a(1, 2);
Vector<float, 2> b = 1 - (a + 2);
Vector<float, 2> c(
1 - (1 + 2),
1 - (2 + 2));
ENSURE(allEqual(b, c));
```

Vector expressions

Vector expressions are as efficient as hand-coded expressions. For example:

```Vector<float, 3> x;
Vector<float, 3> y = 2 * x  + 4;
```

corresponds in performance to:

```y[0] = 2 * x[0] + 4
y[1] = 2 * x[1] + 4
y[2] = 2 * x[2] + 4
```

This is achieved by using expression templates, i.e. by building a compile-time tree of an expression and evaluating it lazily. This converts the evaluation of the expression tree from depth-first to breadth-first.

However, this technique causes a small problem with usability, which you should be aware of: because expressions yield expression objects, function templates that accept Vector's will not match the expression objects. This is because template parameter matching must be exact. The solution is either to evaluate the expression first, or make the function accept a vector expression:

```template <typename Real, int N>
void f(const Vector<Real, N>& v)
{
}

template <typename Real, int N, typename Expression>
void g(const VectorExpression<Real, N, Expression>& v)
{
}

Vector<real, 2> a;
Vector<real, 2> b;

// Compile error.
//f(a * 5 + b);

// Ok
g(a * 5 + b);

// Ok
f(evaluate(a * 5 + b));

// Ok
f(Vector<real, 2>(a * 5 + b));
```

Interoperability

A Vector can be converted to a Tuple with zero overhead, however, a Vector is-not-a Tuple. Conversion to the other direction requires copying: a Vector can be constructed from a Tuple. The Matrix class works together with the Vector class to provide a natural notation for multiplying vectors with matrices. So does the AffineTransformation class.

Convenience functions for static vectors in low dimensions

For working exclusively in a fixed low dimension, such as 2 or 3, Pastel offers some specialized notation. For example, the components in dimension 2 can be accessed by member functions x() and y(). In dimension 3 there is an additional z(). However, maybe the most important one is the ability to construct a vector by listing its components in the constructor:

```Vector<float, 3> a(1, 2, 3);
a.set(1, 2, 3);
a.x() = 1;
a.y() = 2;
a.z() = a.x();
```

Assigning values from a comma-separated list

Vectors can be assigned values by using the following syntax:

```Vector<float> a(ofDimension(8));
a |= 1, 2, 3, 4, 5, 6, 7, 8;
```

Extraneous values are ignored.

Minimal size of static vectors

For static vectors it holds that

```sizeof(Vector<Real, N>) == N * sizeof(Real)
```

This minimality is important because vectors are expected to be stored in large amounts.

Files

A vector expression for a native array.

array_vectorexpression.h

vector_tools.h

vector_tools.hpp

Array comparison for Vectors

allLess, anyLess, allEqual, anyEqual, etc.

vector_compare.h

vector_compare.hpp

Some array programming functions for vectors

min, minIndex, max, maxIndex, permute, clamp, ...

vector_tools_more.h

vector_tools_more.hpp

A vector in R^n

vector.h

vector.hpp

VectorBase class

CRTP base class for Vector

vectorbase.h