Separating Axis Theorem (SAT) convex polygons

Separating Axis Theorem (SAT) - convex polygons

function satOverlap(polyA, polyB):
    axes = getEdgeNormals(polyA) + getEdgeNormals(polyB)
    for axis in axes:
        projA = projectPolygon(polyA, axis)   // returns (min, max)
        projB = projectPolygon(polyB, axis)
        if projA.max < projB.min or projB.max < projA.min:
            return false   // found a separating axis -> no collision
    return true   // no separating axis found on any tested axis -> collision

SAT generalizes this idea to any convex polygon: two convex shapes do not overlap if and only if there exists some axis along which their projections (shadows) don't overlap. It's provably sufficient to only test axes perpendicular to each polygon's edges (the edge normals) — if no separating axis exists among those, the shapes must be colliding. This is more expensive (O(edges) per pair) so it's typically reserved for rotated rectangles or arbitrary convex polygons, not simple grid games.