← Back to index

Polygon collision (Separating Axis Theorem)

Two convex polygons are disjoint iff there is some axis on which their projections don't overlap. The only axes you need to test are the normals of each polygon's edges. The pentagon is fixed; the rotated rectangle follows the mouse.

Note: SAT only works for convex shapes — concave polygons need to be decomposed first.

Pseudocode

for each edge in A's edges + B's edges:
    axis = perpendicular(edge), normalised
    [minA, maxA] = project A onto axis
    [minB, maxB] = project B onto axis
    if maxA < minB or maxB < minA:
        return false           // found a separating axis
return true                    // overlap on every axis = collision

Source

function project(poly, ax, ay) {
    let lo = +Infinity, hi = -Infinity
    for (const v of poly) {
        const d = v.x * ax + v.y * ay
        if (d < lo) lo = d
        if (d > hi) hi = d
    }
    return [lo, hi]
}

function sat(a, b) {
    for (const poly of [a, b]) {
        for (let i = 0; i < poly.length; i++) {
            const p = poly[i]
            const q = poly[(i + 1) % poly.length]
            // edge normal (any consistent perpendicular will do)
            const nx = -(q.y - p.y)
            const ny =   q.x - p.x
            const len = Math.sqrt(nx * nx + ny * ny)
            const ax = nx / len, ay = ny / len
            const [aLo, aHi] = project(a, ax, ay)
            const [bLo, bHi] = project(b, ax, ay)
            if (aHi < bLo || bHi < aLo) return false
        }
    }
    return true
}