Line segments

A wall in a game isn’t an endless line. It starts somewhere and ends somewhere: it’s a line segment. To test against one, we need one new tool, the dot product.

Vectors and the dot product

A vector is a step: how far to move along $x$ and along $y$. The step from point $A$ to point $B$ is the vector

The dot product of two vectors $\mathbf{u}$ and $\mathbf{v}$ multiplies them coordinate by coordinate and adds the results:

It’s also equal to $|\mathbf{u}|\,|\mathbf{v}| \cos\theta$, where $\theta$ is the angle between the two vectors. That tells us what it measures:

• It’s positive when the vectors point roughly the same way, zero when they’re perpendicular, and negative when they point roughly opposite ways.
• When $\mathbf{v}$ has length $1$, $\mathbf{u} \cdot \mathbf{v}$ is how far $\mathbf{u}$ reaches along $\mathbf{v}$: the length of the shadow $\mathbf{u}$ casts onto $\mathbf{v}$.

// A vector is stored like a point: { x, y } is the step, not a position.
function subtract(a: Point, b: Point): Point {
	return { x: a.x - b.x, y: a.y - b.y };
}

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

// A vector is stored like a point: { x, y } is the step, not a position.
function subtract(a, b) {
	return { x: a.x - b.x, y: a.y - b.y };
}

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

# A vector is stored like a point: (x, y) is the step, not a position.
def subtract(a: Point, b: Point) -> Point:
    return Point(a.x - b.x, a.y - b.y)


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

subtract

time O(1) space O(1)

dot

time O(1) space O(1)

Projecting a point onto a segment

Take a segment from $A$ to $B$, its direction $\mathbf{d} = B - A$, and a point $P$. The point of the whole line through $A$ and $B$ that’s closest to $P$ is $A + t\,\mathbf{d}$, where

The top of the fraction is how far $P - A$ reaches along $\mathbf{d}$, and dividing by $\mathbf{d} \cdot \mathbf{d}$ measures that in lengths of the segment. So $t$ says where along the line the closest point is: $0$ at $A$, $1$ at $B$, and in between for points between them. Beyond the ends, $t$ drops below $0$ or rises above $1$, so for the segment, clamp $t$ into $[0, 1]$, just like we clamped the circle’s centre into the rectangle. Then the closest point sits at an end whenever $P$ is past it.

Drag $P$ past either end of the segment and watch $t$ leave $[0, 1]$: the hollow circle is where the projection lands on the whole line, and $Q$ is where clamping puts it back on the segment.

function closestPointOnSegment(p: Point, a: Point, b: Point): Point {
	const d = subtract(b, a);
	const lengthSquared = dot(d, d);
	if (lengthSquared === 0) return a; // A and B are the same point
	const t = clamp(dot(subtract(p, a), d) / lengthSquared, 0, 1);
	return { x: a.x + t * d.x, y: a.y + t * d.y };
}

function closestPointOnSegment(p, a, b) {
	const d = subtract(b, a);
	const lengthSquared = dot(d, d);
	if (lengthSquared === 0) return a; // A and B are the same point
	const t = clamp(dot(subtract(p, a), d) / lengthSquared, 0, 1);
	return { x: a.x + t * d.x, y: a.y + t * d.y };
}

def closest_point_on_segment(p: Point, a: Point, b: Point) -> Point:
    d = subtract(b, a)
    length_squared = dot(d, d)
    if length_squared == 0:  # A and B are the same point
        return a
    t = clamp(dot(subtract(p, a), d) / length_squared, 0, 1)
    return Point(a.x + t * d.x, a.y + t * d.y)

closestPointOnSegment

time O(1) space O(1)

Circle vs line segment

With the closest point $Q$ of the segment, it’s a point-in-circle test once more: the circle touches the segment when $|CQ| \le r$.

function circleSegmentCollide(c: Circle, a: Point, b: Point): boolean {
	return pointInCircle(closestPointOnSegment(c, a, b), c);
}

function circleSegmentCollide(c, a, b) {
	return pointInCircle(closestPointOnSegment(c, a, b), c);
}

def circle_segment_collide(c: Circle, a: Point, b: Point) -> bool:
    return point_in_circle(closest_point_on_segment(c, a, b), c)

circleSegmentCollide

time O(1) space O(1)

This is the test for a ball against a wall, a platform or a paddle, however they’re rotated. The set of all points within some distance of a segment even has a name of its own, a capsule, and it’s a popular shape for game characters for exactly that reason: testing a circle against a capsule is this same test, with the two radii added together.

Line vs line segment

An endless line and a segment touch when the segment’s ends aren’t both on the same side of the line. That’s the side value from the lines chapter: put both ends into $ax + by + c$, and if the two results have different signs, or one of them is $0$, the segment crosses or touches the line. Multiplying them makes that one comparison: the product is negative or zero exactly then.

function lineSegmentCollide(line: Line, a: Point, b: Point): boolean {
	return side(a, line) * side(b, line) <= 0;
}

function lineSegmentCollide(line, a, b) {
	return side(a, line) * side(b, line) <= 0;
}

def line_segment_collide(line: Line, a: Point, b: Point) -> bool:
    return side(a, line) * side(b, line) <= 0

lineSegmentCollide

time O(1) space O(1)

Segment vs segment

Two segments $AB$ and $CD$ cross when $C$ and $D$ are on opposite sides of the line through $A$ and $B$, and $A$ and $B$ are on opposite sides of the line through $C$ and $D$. One of the two isn’t enough: $C$ and $D$ can straddle the line through $AB$ far past the end of $AB$, and the second check is what catches that.

There’s one special case. When all four ends lie on one line, every side value is $0$, and the question becomes whether the two segments overlap along that line. That’s the interval test from the rectangles chapter, on $x$ and on $y$.

function segmentsIntersect(a: Point, b: Point, c: Point, d: Point): boolean {
	const ab = lineThrough(a, b);
	const sc = side(c, ab);
	const sd = side(d, ab);
	if (sc === 0 && sd === 0) {
		// All four ends on one line: they meet only if they overlap along it.
		return (
			overlap(Math.min(a.x, b.x), Math.max(a.x, b.x), Math.min(c.x, d.x), Math.max(c.x, d.x)) &&
			overlap(Math.min(a.y, b.y), Math.max(a.y, b.y), Math.min(c.y, d.y), Math.max(c.y, d.y))
		);
	}
	const cd = lineThrough(c, d);
	return sc * sd <= 0 && side(a, cd) * side(b, cd) <= 0;
}

function segmentsIntersect(a, b, c, d) {
	const ab = lineThrough(a, b);
	const sc = side(c, ab);
	const sd = side(d, ab);
	if (sc === 0 && sd === 0) {
		// All four ends on one line: they meet only if they overlap along it.
		return (
			overlap(Math.min(a.x, b.x), Math.max(a.x, b.x), Math.min(c.x, d.x), Math.max(c.x, d.x)) &&
			overlap(Math.min(a.y, b.y), Math.max(a.y, b.y), Math.min(c.y, d.y), Math.max(c.y, d.y))
		);
	}
	const cd = lineThrough(c, d);
	return sc * sd <= 0 && side(a, cd) * side(b, cd) <= 0;
}

def segments_intersect(a: Point, b: Point, c: Point, d: Point) -> bool:
    ab = line_through(a, b)
    sc = side(c, ab)
    sd = side(d, ab)
    if sc == 0 and sd == 0:
        # All four ends on one line: they meet only if they overlap along it.
        return overlap(
            min(a.x, b.x), max(a.x, b.x), min(c.x, d.x), max(c.x, d.x)
        ) and overlap(min(a.y, b.y), max(a.y, b.y), min(c.y, d.y), max(c.y, d.y))
    cd = line_through(c, d)
    return sc * sd <= 0 and side(a, cd) * side(b, cd) <= 0

segmentsIntersect

time O(1) space O(1)

If you also need where they cross, for the point a bullet hits a wall, say, the side values give that away too. Along $AB$, the side value against $CD$ changes evenly from $s_{A}$ at $A$ to $s_{B}$ at $B$, so it reaches $0$ at $t = \frac{s_{A}}{s_{A} - s_{B}}$, and the crossing point is $A + t\,(B - A)$.

These last two tests are exactly what the next two chapters need: a polygon’s edges are segments.