CoreSource checked

Separating Axis Theorem

Tests convex shape overlap by looking for an axis that separates them.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Intermediate
Family: Collision Detection
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: SAT

Overview

SAT projects shapes onto candidate axes; if any projection intervals do not overlap, the shapes are separate.

Core Concepts

geometric calculationseparating testgeometric predicatecollision detectionspatial relationshipcoordinate calculation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(a v)

Average

O(a v)

Worst

O(a v)

Space

O(1)

When to Use

Use Separating Axis Theorem when you need to project convex shapes onto axes.
Use it for collision detection with inputs like two convex shapes.
Use it when the problem depends on spatial relationships between points, lines, or shapes.
Use it when the Collision Detection tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when floating-point precision or degenerate cases are not handled.
Avoid it when the required output is not overlap result.

What It Does

Projects convex shapes onto axes
Checks interval overlap on each axis

Use Cases

Collision detection
Physics engines
Hit testing convex polygons

Inputs

Two convex shapes

Outputs

Overlap result
Optional penetration direction

Key Formulas (1)

Projection overlap

overlap = min(maxA, maxB) − max(minA, minB)

overlap = min(maxA, maxB) - max(minA, minB)

Detects separation by checking projected intervals on candidate axes.

Pseudocode

1.Build candidate axes from shape normals
2.Project both shapes onto each axis
3.Check whether projection intervals overlap
4.Return separated if any axis has a gap
5.Otherwise report overlap

Canonical Example

Input: points = [(0,0), (2,0), (1,1), (1,0)]
Output: spatial result such as a boundary, intersection, or containment answer
Explanation: Separating Axis Theorem: The algorithm uses geometric tests to reason about the input shapes.

Implementation Notes

Keep the input contract explicit: Two convex shapes.
Use this step as the implementation spine: Build candidate axes from shape normals.
Then preserve the next state change: Project both shapes onto each axis.
Write tests for points on boundaries, equal coordinates, and very small distances.

Common Pitfalls

SAT applies to convex shapes; concave shapes must be decomposed first.
Forgetting collinear, duplicate, overlapping, or boundary cases.
Returning overlap result without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show polygons projected onto an axis with or without interval overlap.

Step 1 of 5: Build candidate axes from shape normals

axis-projections

Notes

Separating Axis Theorem operates in O(a v) time and O(1) space within the Collision Detection family. Key governing relation: overlap = min(maxA, maxB) - max(minA, minB). Often compared with Oriented Bounding Box Intersection and GJK Collision Detection.