Vectors

Vectors as lists, functions and arrows; addition, scaling, dot product and convex combination, on the robot's position.

A3.7Data structuresA level25 min

Where is the robot, which way is it facing, and is that marker in front of it or behind? Each of those answers is a vector. A vector is a data structure as well as a piece of maths: an ordered list of numbers that a program can add, scale and multiply. In this lesson BugBot's position and heading become vectors, and the dot product tells it what is ahead.

Three ways to see a vector

As a list of numbers. [2.0, 3.14159, -1.0, 2.718281828] is a vector with four components. Because each component is a real number, it is called a 4-vector over ℝ, and the set of all such vectors is written ℝ⁴. In a program it is a one-dimensional array. BugBot's position, [x, y], is a 2-vector over ℝ, a member of ℝ².

As a function. A vector can be read as a function that maps each index to a value. For the 4-vector above, the domain is the set of indexes {0, 1, 2, 3} and the co-domain is ℝ:

0 ↦ 2.0,  1 ↦ 3.14159,  2 ↦ -1.0,  3 ↦ 2.718281828

A dictionary represents that function directly: {0: 2.0, 1: 3.14159, 2: -1.0, 3: 2.718281828}. This is useful when most components are zero, as in the word-count vectors of the last lesson: store only the ones that are not.

As an arrow. A 2-vector or 3-vector can be drawn as an arrow from the origin to the point it names. The arrow has a magnitude (its length) and a direction. For [x, y] the magnitude is √(x² + y²), by Pythagoras.

import math

v_list = [2.0, 3.14159, -1.0, 2.718281828]                 # a vector as a list (a 1D array)
v_dict = {0: 2.0, 1: 3.14159, 2: -1.0, 3: 2.718281828}     # the same vector as a function: index -> value
print(v_list[1], v_dict[1])

p = [30, 40]                                               # a position as an arrow from the origin
print("magnitude", math.sqrt(p[0] ** 2 + p[1] ** 2))

Run this in the simulator

Adding and scaling

Vector addition adds matching components: [3, 4] + [1, 2] = [4, 6]. As arrows, it puts the second arrow on the end of the first, so adding a vector to a position translates it: moves it without turning it.

Scalar-vector multiplication multiplies every component by one number, the scalar: 2 × [3, 4] = [6, 8]. It scales the arrow: the same direction, twice as long. A negative scalar reverses the direction.

Convex combination

A convex combination of two vectors u and v is

αu + βv,  where α ≥ 0, β ≥ 0 and α + β = 1

Every convex combination lies on the straight line segment between the points u and v. With α = 1 you get u, with β = 1 you get v, and with α = β = 0.5 you get the midpoint. So convex combinations let a robot find any point between two places: 25% of the way, halfway, three quarters.

Dot product

The dot product of two vectors of the same size multiplies matching components and adds the results. The answer is a single number, not a vector:

u · v = u₀v₀ + u₁v₁ + ... + uₙ₋₁vₙ₋₁

For u = [3, 4] and v = [1, 2]: u · v = 3 × 1 + 4 × 2 = 11.

Its most useful property connects it to the angle θ between the arrows:

u · v = |u| × |v| × cos θ

• Finding the angle: θ = cos⁻¹((u · v) / (|u| × |v|)). For the example, |u| = 5 and |v| = √5 ≈ 2.236, so cos θ = 11 / 11.18 ≈ 0.984 and θ ≈ 10.3°.
• Perpendicular: if u · v = 0 the vectors are at right angles.
• In front or behind: if u · v > 0 the angle is less than 90°; if it is negative, more than 90°.
• Magnitude: u · u = |u|², so |u| = √(u · u).
• How far along: if h is a unit vector (magnitude 1), then h · d is how far d reaches in the direction of h.

BugBot's vectors

position() gives the robot's position vector p. Its heading, θ degrees clockwise from the direction it started in, gives a unit heading vector h = [sin θ, cos θ]: at 0° that is [0, 1], straight ahead, and at 90° it is [1, 0], to the right. For a target at t, the displacement from the robot is d = t - p, and h · d says whether the target is ahead, and how far along the heading it is.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
import math

def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]

turn_right(30, angle=60)
theta = math.radians(heading())
h = [math.sin(theta), math.cos(theta)]
p = list(position())
print("heading vector", [round(h[0], 2), round(h[1], 2)])

targets = {"cone": [30, 20], "box": [-20, 10], "wall": [10, -40]}
for name in targets:
    t = targets[name]
    d = [t[0] - p[0], t[1] - p[1]]
    along = dot(h, d)
    angle = math.degrees(math.acos(along / math.sqrt(dot(d, d))))
    print(name, "is", "ahead" if along > 0 else "behind", "at", round(angle), "degrees off the heading")

d = [targets["cone"][0] - p[0], targets["cone"][1] - p[1]]
forward(50, distance=dot(h, d))       # drive as far along the heading as the cone reaches
print("now at", position())

Run this in the simulator

The cone is almost straight ahead, so driving h · d along the heading brings the robot very close to it. The other two targets have negative dot products: they are behind.

Task: meet on the line

Two beacons are at u = [40, 20] and v = [-20, 60], in cm from the robot's start (x to the right, y forward). Write these three functions yourself, for vectors of any length, without numpy:

• add(a, b): returns a new list, the vector sum of a and b.
• scale(k, a): returns a new list, the number k times the vector a.
• dot(a, b): returns the dot product of a and b, a single number.

Then print, in this order:

1. u.v = <dot product>, which is a whole number.
2. angle = <angle> degrees, the angle between u and v rounded to a whole number with round(). You will need math.acos, math.degrees and math.sqrt.
3. w = <w>, where w = 0.25u + 0.75v, built with scale and add, printed as a Python list, for example w = [1.0, 2.0].

Finally drive to w: slide sideways by its x component (left if it is negative) and then forward by its y component.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
import math

u = [40, 20]
v = [-20, 60]

Challenges

1. Is w really on the segment between the beacons? Check that w - u is a positive scalar multiple of v - u.
2. Find two different whole-number vectors whose dot product with [3, 4] is zero. What do they have in common?
3. Rewrite dot so it takes two vectors stored as dictionaries, where missing indexes mean zero.