Rectangles · Collision detection for beginners

Intervals on a line

Back on a single number axis. A segment from $a_{1}$ to $a_{2}$ is the interval $[a_{1}, a_{2}]$ . Two intervals $[a_{1}, a_{2}]$ and $[b_{1}, b_{2}]$ overlap unless one ends before the other begins, so they overlap exactly when

a_{1} \le b_{2} \quad \text{and} \quad b_{1} \le a_{2}

TypeScript

function overlap(a1: number, a2: number, b1: number, b2: number): boolean {
	return a1 <= b2 && b1 <= a2;
}

JavaScript

function overlap(a1, a2, b1, b2) {
	return a1 <= b2 && b1 <= a2;
}

Python

def overlap(a1: float, a2: float, b1: float, b2: float) -> bool:
    return a1 <= b2 and b1 <= a2

overlap: time O(1) space O(1)

Rectangle vs rectangle

A rectangle whose sides run along the axes is called an axis-aligned bounding box, or AABB. With its corner at $(x, y)$ , width $w$ and height $h$ , it’s nothing more than two intervals: $[x, x + w]$ on the $x$ -axis and $[y, y + h]$ on the $y$ -axis.

Two AABBs collide when their intervals overlap on the $x$ -axis and on the $y$ -axis. If there’s a gap on either axis, you can slide a straight line between them.

Drag either rectangle. x: [130, 320] and [380, 530] don’t overlap · y: [60, 180] and [130, 240] overlap → apart

TypeScript

type Rect = { x: number; y: number; w: number; h: number };

function rectsCollide(a: Rect, b: Rect): boolean {
	return (
		overlap(a.x, a.x + a.w, b.x, b.x + b.w) &&
		overlap(a.y, a.y + a.h, b.y, b.y + b.h)
	);
}

JavaScript

// A rectangle is an object like { x: 20, y: 40, w: 120, h: 80 }.
function rectsCollide(a, b) {
	return (
		overlap(a.x, a.x + a.w, b.x, b.x + b.w) &&
		overlap(a.y, a.y + a.h, b.y, b.y + b.h)
	);
}

Python

@dataclass
class Rect:
    x: float
    y: float
    w: float
    h: float


def rects_collide(a: Rect, b: Rect) -> bool:
    return (
        overlap(a.x, a.x + a.w, b.x, b.x + b.w)
        and overlap(a.y, a.y + a.h, b.y, b.y + b.h)
    )

rectsCollide: time O(1) space O(1)

AABBs are so cheap that games often wrap complicated shapes in one, and only run the exact test when the boxes overlap.

Circle vs rectangle

Find the point $Q$ of the rectangle that is closest to the circle’s centre $C$ , and it’s a point-in-circle test again. Finding $Q$ takes no geometry at all: clamp each coordinate of $C$ into the rectangle’s interval on that axis.

Q = \big(\operatorname{clamp}(x_{C},\, x,\, x + w),\ \operatorname{clamp}(y_{C},\, y,\, y + h)\big)

When the centre is inside the rectangle, $Q$ is the centre itself, the distance is $0$ , and the test rightly says they collide.

Drag the circle or the rectangle. Q = (clamp(480, 200, 390), clamp(230, 80, 210)) = (390, 210) · |CQ| = 92 > r = 50 → apart

TypeScript

function clamp(value: number, min: number, max: number): number {
	return Math.max(min, Math.min(max, value));
}

function circleRectCollide(c: Circle, rect: Rect): boolean {
	const closest = {
		x: clamp(c.x, rect.x, rect.x + rect.w),
		y: clamp(c.y, rect.y, rect.y + rect.h)
	};
	return pointInCircle(closest, c);
}

JavaScript

function clamp(value, min, max) {
	return Math.max(min, Math.min(max, value));
}

function circleRectCollide(c, rect) {
	const closest = {
		x: clamp(c.x, rect.x, rect.x + rect.w),
		y: clamp(c.y, rect.y, rect.y + rect.h)
	};
	return pointInCircle(closest, c);
}

Python

def clamp(value: float, low: float, high: float) -> float:
    return max(low, min(high, value))


def circle_rect_collide(c: Circle, rect: Rect) -> bool:
    closest = Point(
        clamp(c.x, rect.x, rect.x + rect.w),
        clamp(c.y, rect.y, rect.y + rect.h),
    )
    return point_in_circle(closest, c)

clamp: time O(1) space O(1)
circleRectCollide: time O(1) space O(1)

Intervals on a line

Rectangle vs rectangle

Circle vs rectangle

Comments