Separating Axes and Support Functions for Convex Intersection Tests

Two convex polygons in the plane either intersect or are separated by a line. That statement is the geometric form of the separating hyperplane theorem, and it converts an intersection test into a search for a direction: find an axis along which the projections of the two bodies are disjoint, and the bodies are disjoint. If no such axis exists, they intersect. For polygons the search can be restricted to a finite set of candidate axes — the edge normals — which makes the test exact and cheap. For smooth or curved convex bodies the candidate set is infinite, and the test becomes an optimisation over directions, which is where support functions and the Gilbert–Johnson–Keerthi algorithm enter.

The two approaches share a single underlying object. The Minkowski difference of bodies A and B is the set of all points a − b for a in A and b in B. It contains the origin exactly when A and B intersect, because the origin corresponds to a = b. Testing intersection is therefore testing containment of a point in a convex set, and every method in this area is a way of answering that question without constructing the set.

Projections and the finite axis set

For two convex polygons with edge normals n_1 … n_m and m_1 … m_k, the projections onto an axis are intervals, and the intervals are disjoint exactly when the polygons are disjoint. It is enough to test the normals of the edges: if the polygons are separated by any line at all, they are separated by a line parallel to an edge of one of them. The argument is that the closest pair of points between two disjoint convex polygons either consists of a vertex and an edge interior, in which case the connecting segment is perpendicular to that edge, or of two vertices, in which case the direction from each vertex toward the other lies in the cone spanned by the normals of the edges meeting at it. In both cases an axis parallel to one of those edge normals separates the two projections, so the finite set of edge normals is enough.

The test on one axis is a min-max over vertices, which for a polygon with n vertices is O(n). Testing all m + k edge normals therefore costs O((m + k)²), which is the naive bound and the one the straightforward implementation achieves. For convex polygons the projections can be maintained incrementally as the axis rotates, since the extreme vertex changes monotonically around the polygon, which brings the whole test down to O(m + k) with a rotating-calipers pass. Most implementations do not bother: polygons in a collision system rarely have more than a few dozen vertices, and the quadratic constant is small.

def project(poly, axis):
    """Min and max of the dot product of poly's vertices with a unit axis."""
    dots = [x * axis[0] + y * axis[1] for x, y in poly]
    return min(dots), max(dots)

def separated(a, b):
    """True if some edge normal separates the two convex polygons."""
    for poly in (a, b):
        for i in range(len(poly)):
            x1, y1 = poly[i]
            x2, y2 = poly[(i + 1) % len(poly)]
            n = (y1 - y2, x2 - x1)          # normal of this edge; sign is irrelevant
            length = (n[0] ** 2 + n[1] ** 2) ** 0.5
            axis = (n[0] / length, n[1] / length)
            a_lo, a_hi = project(a, axis)
            b_lo, b_hi = project(b, axis)
            if a_hi < b_lo or b_hi < a_lo:
                return True                 # found a separating axis
    return False

Normalising the axis is not required for the boolean result, since scaling an axis scales both intervals by the same positive factor and cannot change whether they overlap. It matters only when the interval gaps are compared against a tolerance, because an unnormalised axis makes the gap proportional to the edge length and the tolerance meaningless.

The comparison a_hi < b_lo uses strict inequality, which means polygons that touch along a face or at a vertex are classified as intersecting. That is the right convention for most callers, and the wrong one for a few: a stack of boxes resting on each other should not report collisions between neighbours. The fix is a tolerance on the comparison, and any tolerance reintroduces the scale-dependence problem discussed in exact geometric predicates. The alternative is to allow touching as intersecting and to let the caller’s response to a collision resolve resting contact, which is the usual convention for collision code.

Support functions and the Minkowski difference

The support function of a convex body in direction d returns the point of the body farthest along d, that is, the maximiser of the dot product with d. For a polygon it is a scan over vertices; for a sphere it is the centre plus the radius times the unit direction; for a capsule it is the segment’s endpoint in that direction plus the radius. The function is the only thing an algorithm needs to know about a body, which is why the same code handles polygons, ellipsoids, and convex hulls of arbitrary point sets.

The support function of the Minkowski difference is the difference of the support functions: the farthest point of A − B along d is support(A, d) − support(B, −d). This identity is the whole basis of the algorithms below. It means the difference set can be queried in any direction at the cost of two support queries on the original bodies, and never needs to be materialised. For two polygons with m and k vertices, one support query costs O(m) and O(k) with a linear scan, or O(log m) and O(log k) if the vertices are stored in angular order and searched by binary search.

GJK as a simplex search in the difference set

Gilbert, Johnson, and Keerthi described an algorithm that finds the point of the Minkowski difference closest to the origin, or determines that the origin is inside it. It maintains a simplex of support points from the difference set, which is a point, a segment, a triangle, or a tetrahedron in 3D, and iteratively improves it.

The loop is: given the current simplex, find the point of the simplex closest to the origin. If that point is the origin, the bodies intersect. Otherwise use the direction from the closest point to the origin as the next search direction, query the support function of the difference in that direction, and add the resulting point to the simplex. If the new point does not get closer to the origin than the current simplex does, the minimum has been found and the bodies are disjoint, with the distance given by the closest point.

The convergence argument is that each iteration strictly reduces the distance from the origin to the simplex, and the reduction is bounded below by a factor related to the simplex’s geometry. In exact arithmetic the loop terminates; in floating point it can cycle, which is why implementations add a maximum iteration count and a relative-improvement threshold. The usual failure mode is not a wrong answer but a non-termination on configurations where the bodies are nearly touching and the improvement per iteration falls below the rounding noise.

For polygons, GJK is usually overkill: the finite normal set gives an exact answer in linear time with no iteration. GJK earns its place when the bodies are curved, when they are defined implicitly by support functions, or when the distance between them is needed rather than just the boolean. The distance output is the same quantity computed by the closest-point routine, and it is what makes GJK the standard choice for continuous collision detection, where the time of impact is derived from the distance and its rate of change.

Where both approaches fail

The finite-axis test assumes both bodies are convex. Applied to a concave polygon it reports intersections that do not exist, because a concave shape’s projection can overlap another’s on every axis while the shapes are disjoint. The fix is to decompose the concave polygon into convex pieces first, which for a simple polygon can be done by triangulation, and then test every pair of pieces. A triangulation produced by Delaunay triangulation and the empty circumcircle test gives a decomposition with good aspect ratios, though a constrained triangulation is needed when the polygon has holes. The pair count grows quadratically with the number of pieces, which is why decomposition quality matters: a decomposition into a few dozen convex parts is workable, one into thousands is not.

The Minkowski difference of two convex polygons has up to m + k vertices, and its construction is O(m + k) by merging the two edge sequences by angle, the same merge that computes the convex hull of a union. Building it is cheap for polygons but defeats the purpose for curved bodies, where the vertex count is unbounded. That is the trade: explicit construction is simple and exact for polygons, and support-function methods avoid it at the cost of iteration and approximation.

Numerical conditioning is the other limit. When the bodies are nearly touching, the closest point is near the origin and the direction used for the next support query is poorly determined; small errors in the direction produce support points that are nearly duplicates, and the simplex update becomes degenerate. Implementations detect duplicate support points and terminate, which converts a would-be infinite loop into a slightly inaccurate distance, and that is the correct trade for a collision system that must never hang.

Choosing between this and a full arrangement

For a small number of convex bodies, pairwise support-function tests are the right tool, and their cost is linear in the number of vertices per test. For many bodies, the bottleneck becomes the number of pairs, and the answer is a broad phase that prunes pairs by bounding volume before the narrow phase runs. For computing the actual intersection polygon of two convex shapes, rather than just testing it, the standard method is half-plane clipping: clip one polygon against each edge of the other, which is O(m·k) and produces the intersection as a convex polygon. The same clipping idea underlies the polygon boolean operations that generalise this test to arbitrary shapes, and the separating-axis test is the cheap predicate that decides whether the expensive construction is worth starting at all.

The dual view is worth keeping in mind: a convex body is the intersection of half-planes, so a test for intersection of two bodies is a feasibility question for a system of linear inequalities, and the separating axis is a certificate of infeasibility by a single inequality. That framing connects the test to linear programming in fixed dimension, where the same structure — a small certificate that can be checked in linear time — is what makes the algorithms practical.