Circles · Collision detection for beginners

Every test in this chapter compares squared distances, with the squared distance function from the chapter on distance between two points:

TypeScript

type Point = { x: number; y: number };

function distanceSquared(a: Point, b: Point): number {
	return (b.x - a.x) ** 2 + (b.y - a.y) ** 2;
}

JavaScript

function distanceSquared(a, b) {
	return (b.x - a.x) ** 2 + (b.y - a.y) ** 2;
}

Python

import math
from dataclasses import dataclass


@dataclass
class Point:
    x: float
    y: float


def distance_squared(a: Point, b: Point) -> float:
    return (b.x - a.x) ** 2 + (b.y - a.y) ** 2

distanceSquared: time O(1) space O(1)

The equation of a circle

A circle is the set of all points at the same distance $r$ from its centre $S(a, b)$ . Write that sentence with the distance formula, square both sides, and you have the equation of a circle:

(x - a)^2 + (y - b)^2 = r^2

Points inside the circle are closer to the centre than $r$ , so they satisfy the inequality

(x - a)^2 + (y - b)^2 \le r^2

Point vs circle

That inequality already is a collision test. Is the cursor over a round button? Did a bullet hit a round enemy?

Drag P or the centre S. (x − a)² + (y − b)² = 180² + (−70)² = 37300 > r² = 10000 → P is outside

TypeScript

type Circle = { x: number; y: number; r: number };

function pointInCircle(p: Point, c: Circle): boolean {
	return distanceSquared(p, c) <= c.r ** 2;
}

JavaScript

// A circle is an object like { x: 200, y: 150, r: 40 }.
function pointInCircle(p, c) {
	return distanceSquared(p, c) <= c.r ** 2;
}

Python

@dataclass
class Circle:
    x: float
    y: float
    r: float


def point_in_circle(p: Point, c: Circle) -> bool:
    return distance_squared(p, c) <= c.r ** 2

pointInCircle: time O(1) space O(1)

A circle has an $x$ and a $y$ like a point, so the distance functions from the previous chapters take it as it is.

Circle vs circle

Two circles touch when the distance between their centres is at most the sum of their radii:

|S_{1}S_{2}| \le r_{1} + r_{2}

Another way to see it: grow one circle by the other’s radius, shrink the other one to a point, and you’re back to a point-in-circle test.

Drag either circle. |S₁S₂| = 255 > r₁ + r₂ = 90 + 55 = 145 → apart

TypeScript

function circlesCollide(a: Circle, b: Circle): boolean {
	return distanceSquared(a, b) <= (a.r + b.r) ** 2;
}

JavaScript

function circlesCollide(a, b) {
	return distanceSquared(a, b) <= (a.r + b.r) ** 2;
}

Python

def circles_collide(a: Circle, b: Circle) -> bool:
    return distance_squared(a, b) <= (a.r + b.r) ** 2

circlesCollide: time O(1) space O(1)

The circles on my home page run exactly this test.

The equation of a circle

Point vs circle

Circle vs circle

Comments