Coordinates and distance in space

Part II takes the book into space. Most of Part I carries straight over with one more coordinate: a circle becomes a sphere, a rectangle becomes a box, and every test gains a term. A few ideas are new, because space has room for them: the cross product, planes and rays.

The Cartesian coordinate system in space

In space, the Cartesian coordinate system is three mutually perpendicular number axes, the $x$-, $y$- and $z$-axis, that intersect at the origin. Every point in space is represented by exactly one ordered triple $(x, y, z)$.

Which way is up

A third axis means one more decision: which way it points. This book draws $y$ up and $z$ towards you, like Three.js, Godot and OpenGL. Unity turns $z$ away from you, and Unreal and Blender put $z$ up. None of the tests in this book care which axis is which, as long as every part of a program agrees.

The figures in Part II are drawn in 3D. Drag the background of one to turn it, and drag a point or a shape to move it. It moves parallel to your screen, so to move something towards you or away, turn the view first. The dashed line under each point drops straight down to the floor, the plane $y = 0$, which is how you can tell where it is.

Vectors in space

A vector in space is a step along three axes, $(x, y, z)$, and it’s stored the same way as a point. The step from $A$ to $B$ and the dot product each gain a third term:

The dot product means just what it did in the chapter on line segments: it’s positive when two vectors point roughly the same way, zero when they’re perpendicular and negative when they point roughly opposite ways, and with a vector of length $1$ it measures how far the other one reaches along it.

// A point, or a vector: { x, y, z } is then the step, not a position.
type Vec3 = { x: number; y: number; z: number };

function subtract(a: Vec3, b: Vec3): Vec3 {
	return { x: a.x - b.x, y: a.y - b.y, z: a.z - b.z };
}

function dot(u: Vec3, v: Vec3): number {
	return u.x * v.x + u.y * v.y + u.z * v.z;
}

// A point or a vector is an object like { x: 1, y: 2, z: 3 }.
function subtract(a, b) {
	return { x: a.x - b.x, y: a.y - b.y, z: a.z - b.z };
}

function dot(u, v) {
	return u.x * v.x + u.y * v.y + u.z * v.z;
}

import math
from dataclasses import dataclass


@dataclass
class Vec3:
    """A point, or a vector: (x, y, z) is then the step, not a position."""

    x: float
    y: float
    z: float


def subtract(a: Vec3, b: Vec3) -> Vec3:
    return Vec3(a.x - b.x, a.y - b.y, a.z - b.z)


def dot(u: Vec3, v: Vec3) -> float:
    return u.x * v.x + u.y * v.y + u.z * v.z

subtract

time O(1) space O(1)

dot

time O(1) space O(1)

Part II’s functions reuse Part I’s names, subtract and dot included, so keep them in their own file, or module, next to Part I’s.

Distance between two points in space

The distance between two points $A(x_{1}, y_{1}, z_{1})$ and $B(x_{2}, y_{2}, z_{2})$ in space is also the hypotenuse of a right triangle, $ACB$. It just takes one more right triangle, $ADC$, lying flat underneath it, to get the length of the leg $AC$ first. From $A$, go along the $x$-axis to $D$, then along the $z$-axis to $C$, then straight up to $B$:

From triangle $ADC$:

and from triangle $ACB$:

Move $A$ and $B$ around, and turn the view until you can see that $ADC$ lies flat and $ACB$ stands straight up.

Each extra dimension just adds one more squared difference under the root. Math.hypot and Python’s math.hypot take any number of them.

The trick from Part I works here too: to compare distances, compare their squares and skip the root. And the squared distance of two points is the step between them, dotted with itself.

function distance(a: Vec3, b: Vec3): number {
	return Math.hypot(b.x - a.x, b.y - a.y, b.z - a.z);
}

function distanceSquared(a: Vec3, b: Vec3): number {
	const step = subtract(b, a);
	return dot(step, step);
}

function distance(a, b) {
	return Math.hypot(b.x - a.x, b.y - a.y, b.z - a.z);
}

function distanceSquared(a, b) {
	const step = subtract(b, a);
	return dot(step, step);
}

def distance(a: Vec3, b: Vec3) -> float:
    return math.hypot(b.x - a.x, b.y - a.y, b.z - a.z)


def distance_squared(a: Vec3, b: Vec3) -> float:
    step = subtract(b, a)
    return dot(step, step)

distance

time O(1) space O(1)

distanceSquared

time O(1) space O(1)

Midpoint in space

The point halfway between $A$ and $B$ is still the average of their coordinates, all three of them:

It’s also the centre of the box that has $A$ and $B$ as opposite corners, which the chapter on boxes comes back to.

function midpoint(a: Vec3, b: Vec3): Vec3 {
	return { x: (a.x + b.x) / 2, y: (a.y + b.y) / 2, z: (a.z + b.z) / 2 };
}

function midpoint(a, b) {
	return { x: (a.x + b.x) / 2, y: (a.y + b.y) / 2, z: (a.z + b.z) / 2 };
}

def midpoint(a: Vec3, b: Vec3) -> Vec3:
    return Vec3((a.x + b.x) / 2, (a.y + b.y) / 2, (a.z + b.z) / 2)

midpoint

time O(1) space O(1)