SEPARATING AXIS a gap on one axis proves no collision
Two convex shapes miss each other if and only if there is some direction along which their shadows don’t overlap. For polygons you need only test a finite set of directions — the edge normals — and the moment one shows a gap, you stop: they cannot be colliding. It is the collision test in countless 2-D game engines, and it is Minkowski’s 1896 hyperplane-separation theorem in a game-dev costume.
THE TECHNIQUE project onto each edge normal; find a gap
For each edge of each polygon, take the perpendicular (the candidate axis) and project every vertex of both shapes onto it, getting two intervals. If the intervals are disjoint on any axis, a gap exists — the shapes are separated, done. Only if every axis overlaps are they colliding. Below: two triangles; the axis (1,0) shows a gap of 1. live demo
HISTORY & CREDIT 1896 theorem, 1996 name
“SAT is a classical math theorem name” — yes no; mathematicians call it the hyperplane separation theorem. “Separating Axis” is a graphics label. cited
1896 · Hermann Minkowski (Geometrie der Zahlen) proves disjoint convex sets admit a separating hyperplane — an existence result, no algorithm. 1990 · David Baraff (SIGGRAPH) maintains a separating plane through a face of a polytope for rigid-body simulation — the general polytope reduction. 1996 · Gottschalk, Lin & Manocha (OBBTree) systematize the 15-axis test for oriented boxes (3+3 face normals + 9 edge-edge cross products); Chris Hecker’s magazine columns put it in front of every game developer. the 2-D trap · in 2-D you test only edge normals; in 3-D that is insufficient — you must add the 9 edge×edge cross-products, or two boxes can pass an edge-on-edge separation and report a false collision.
Convex-only (a concave shape must be decomposed first), and the “axis” is the line orthogonal to the separating plane. Minkowski 1896 / GLM 1996
RECOMMEND FOR I-13 parallel arrays, no sqrt, no matrix
Vertices as two parallel arrays; the whole test is subtract / multiply / compare — and the gap decides it:
$ i13 run sat.i13 # A={(0,0),(4,0),(0,3)} B={(5,0),(9,0),(9,3)}
axis (1,0): proj A = [0,4] proj B = [5,9] gap = 1
maxA(4) < minB(5) -> separated = 1 DISJOINT, no collision
Recommend:nothing new — hold each polygon as two parallel f64 arrays xs[], ys[] (the PS-004 sidestep: no 2-D array, no struct-of-pairs); each edge normal is (−Δy, Δx), projection is a dot product, and the overlap test is min/max compares (verified axis (1,0): A=[0,4], B=[5,9], gap 1, separated). And the usual sqrt normalization is a myth-cost — scaling an axis scales both intervals equally, so raw +,−,× suffice. Note: the honest scope limit is dimensional — the 2-D edge-normal test lands cleanly, but 3-D needs the 9 edge-edge cross-product axes too, which the corpus can compute but this dart does not.