Vectors

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

A3.7Data structuresA level25 min

Covers AQA 7517 4.2.1.4 Abstract data types/data structures · AQA 7517 4.2.8.1 Vectors

Print it: worksheet (PDF) · answers (PDF) · as a web page

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.