Lines

The equation of a line

The line you probably know from school is $y = kx + q$, where $k$ is the slope and $q$ is where the line crosses the $y$-axis. It has one flaw for games: a vertical line has no slope, so it can’t be written that way. The general equation of a line covers every line:

For a line through two points $P_{1}(x_{1}, y_{1})$ and $P_{2}(x_{2}, y_{2})$, one choice of coefficients is

The vector $(a, b)$ is the line’s normal vector. It points straight out of the line, perpendicular to it.

Drag the two points below and watch the coefficients follow. Whenever the line isn’t vertical, the slope form can be read straight off them, $k = -\frac{a}{b}$ and $q = -\frac{c}{b}$. Now line the points up vertically: $b$ becomes $0$, the slope form has nothing to divide by, and $ax + by + c = 0$ carries on as if nothing happened.

type Line = { a: number; b: number; c: number };

function lineThrough(p1: Point, p2: Point): Line {
	return { a: p2.y - p1.y, b: p1.x - p2.x, c: p2.x * p1.y - p1.x * p2.y };
}

// A line is an object like { a: 1, b: -2, c: 5 }, for x - 2y + 5 = 0.
function lineThrough(p1, p2) {
	return { a: p2.y - p1.y, b: p1.x - p2.x, c: p2.x * p1.y - p1.x * p2.y };
}

@dataclass
class Line:
    a: float
    b: float
    c: float


def line_through(p1: Point, p2: Point) -> Line:
    return Line(p2.y - p1.y, p1.x - p2.x, p2.x * p1.y - p1.x * p2.y)

lineThrough

time O(1) space O(1)

Which side of a line a point is on

Put any point $(x_{0}, y_{0})$ into the left-hand side of the equation. For a point on the line, you get $0$, which is what the equation says. For a point off the line, you get a number whose sign tells you which side of the line the point is on: positive on the side the normal vector $(a, b)$ points to, negative on the other. Every chapter from here on leans on this one number.

// ax + by + c for the point: 0 on the line, and its sign says which side.
function side(p: Point, line: Line): number {
	return line.a * p.x + line.b * p.y + line.c;
}

// ax + by + c for the point: 0 on the line, and its sign says which side.
function side(p, line) {
	return line.a * p.x + line.b * p.y + line.c;
}

def side(p: Point, line: Line) -> float:
    """ax + by + c for the point: 0 on the line, and its sign says which side."""
    return line.a * p.x + line.b * p.y + line.c

side

time O(1) space O(1)

The sign is useful on its own, too: it tells you which side of a wall the player is on.

Distance from a point to a line

The size of that number grows with the distance from the line, multiplied by the length of the normal vector, $\sqrt{a^2 + b^2}$. Divide that length out and you have the distance:

Drag $P$ across the line and watch the sign flip, and the distance shrink to $0$ on the line itself.

function distanceToLine(p: Point, line: Line): number {
	return Math.abs(side(p, line)) / Math.hypot(line.a, line.b);
}

function distanceToLine(p, line) {
	return Math.abs(side(p, line)) / Math.hypot(line.a, line.b);
}

def distance_to_line(p: Point, line: Line) -> float:
    return abs(side(p, line)) / math.hypot(line.a, line.b)

distanceToLine

time O(1) space O(1)

Circle vs line

A circle touches a line when its centre is at most $r$ away from it. With the squaring trick, that’s $(ax_{0} + by_{0} + c)^2 \le r^2(a^2 + b^2)$: no root, and no division.

function circleLineCollide(c: Circle, line: Line): boolean {
	return side(c, line) ** 2 <= c.r ** 2 * (line.a ** 2 + line.b ** 2);
}

function circleLineCollide(c, line) {
	return side(c, line) ** 2 <= c.r ** 2 * (line.a ** 2 + line.b ** 2);
}

def circle_line_collide(c: Circle, line: Line) -> bool:
    return side(c, line) ** 2 <= c.r ** 2 * (line.a ** 2 + line.b ** 2)

circleLineCollide

time O(1) space O(1)

This line never ends. Walls and platforms do, which is what the next chapter is about.