Separating axis theorem

The separating axis theorem states that for two convex polygons, there exists a line (the separating axis) perpendicular to one of the polygons' edges such that, if the polygons' projections onto that line do not overlap, the polygons do not intersect. The theorem transforms the two-dimensional intersection problem into a series of one-dimensional interval-overlap tests, making it the dominant algorithm for exact collision detection between convex shapes in computer graphics and physics engines.

The theorem holds only for convex shapes; non-convex polygons must be decomposed into convex pieces or approximated with bounding convex hulls. For two polygons with m and n edges, the test requires at most m + n projections. In practice, most tests terminate early: the first non-overlapping projection proves separation, and no further tests are needed. This early-exit property makes the separating axis theorem surprisingly efficient despite its worst-case linear complexity.

The theorem is a specific instance of a broader principle in computational geometry: project to simplify. By projecting complex shapes onto carefully chosen axes, a hard geometric problem becomes a simple arithmetic one. The choice of axes — the edges of the polygons — is not arbitrary; it is the minimal set guaranteed to detect separation if separation exists. This optimality is what makes the theorem both elegant and practical.