1 Introduction
This document describes the method of separating axes, a method for determining whether or not two
stationary convex objects are intersecting. The ideas can be extended to handle moving convex objects and
are useful for predicting collisions of the objects and for computing the first time of contact. The current
focus of this document is on the test intersection geometric query, a query that just indicates whether or
not an intersection exists or will occur when the objects are moving. The problem of computing the set of
intersection is denoted a find intersections geometric query and is generally more difficult to implement than
the test intersection query. Information from the test query can help determine the contact set that the find
query must construct. This document will describe in what way the test query information can be used.
2 Separation by Projection onto a Line
A test for nonintersection of two convex objects is simply stated: If there exists a line for which the intervals
of projection of the two objects onto that line do not intersect, then the objects are do not intersect. Such
a line is called a separating line or, more commonly, a separating axis. The translation of a separating line
is also a separating line, so it is sufficient to consider lines that contain the origin. Given a line containing
the origin and with unit-length direction D, the projection of a compact
1
, convex
2
set C onto the line is the
interval
I = [λ
min
(D), λ
max
(D)] = [min{D · X : X ∈ C}, max{D · X : X ∈ C}].
Two compact convex sets C
0
and C
1
are separated if there exists a direction D such that the projection
intervals I
0
and I
1
do not intersect. Specifically they do not intersect when
λ
(0)
min
(D) > λ
(1)
max
(D) or λ
(0)
max
(D) < λ
(1)
min
(D). (1)
The superscript corresponds to the index of the convex set. Although the comparisons are made where D
is unit length, the comparison results are invariant to changes in length of the vector. This follows from
λ
min
(tD) = tλ
min
(D) and λ
max
(tD) = tλ
max
(D) for t > 0. The Boolean value of the pair of comparisons is
also invariant when D is replaced by the opposite direction −D. This follows from λ
min
(−D) = −λ
max
(D)
and λ
max
(−D) = −λ
min
(D). When D is not unit length, the intervals obtained for the separating axis tests
are not the projections of the object onto the line, rather they are scaled versions of the projection intervals.
I make no distinction in this document between the scaled projection and regular projection. I will also use
the terminology that the direction vector for a separating axis is called a separating direction, a direction
that is not necessarily unit length.
3 Separation of Convex Polygons in 2D
For a pair of convex polygons in 2D, only a finite set of direction vectors needs to be considered for separation
tests. That set includes the normal vectors to the edges of the polygons. The left picture in Figure 3.1 shows
1
A set is compact if it is closed and bounded. To illustrate in one dimension, the interval [0, 1] is closed and bounded, so it
is compact. The interval [0, 1) is bounded, but not closed since it does not contain the limiting point 1, so it is not compact.
The interval [0, ∞) is closed, but not bounded, so it is not compact.
2
A set is convex if given any two points P and Q in the set, the line segment (1 − t)P + tQ for t ∈ [0, 1] is also in the set.
In one dimension, both [0, 1] and [0, 1) are convex.
2
