Collision Detection Using the Separating Axis Theorem
The Separating Axis Theorem is often used to check for collisions between two simple polygons, or between a polygon and a circle. As with all algorithms, it has its strengths and its weaknesses. In this tutorial, we'll go over the math behind the theorem, and show how it can be used in game development with some sample code and demos.
Note: Although the demos and sourcecode of this tutorial use Flash and AS3, you should be able to use the same techniques and concepts in almost any game development environment.
What the Theorem States
The Separating Axis Theorem (SAT for short) essentially states if you are able to draw a line to separate two polygons, then they do not collide. It's that simple.
In the diagram above, you can easily see collisions occurring in the second row. However you try to squeeze a line in between the shapes, you will fail. The first row is exactly the opposite. You can easily draw a line to separate the shapes  and not just one line, but a lot of them:
Okay, let's not overdo this; I think you get the point. The key argument here is that if you can draw such a line, then there must be a gap separating the shapes. So how do we check for this?
Projection Along an Arbitrary Axis
Let's assume for now that the polygons we refer to are squares: box1
on the left and box2
on the right. It's easy to see that these squares are horizontally separated. A straightforward approach to determine this in code is to calculate the horizontal distance between the two squares, then subtract the halfwidths of box1
and box2
:
1 
//Pseudo code to evaluate the separation of box1 and box2

2 
var length:Number = box2.x  box1.x; 
3 
var half_width_box1:Number = box1.width*0.5; 
4 
var half_width_box2:Number = box2.width*0.5; 
5 

6 
var gap_between_boxes:Number = length  half_width_box1  half_width_box2; 
7 
if(gap_between_boxes > 0) trace("It's a big gap between boxes") 
8 
else if(gap_between_boxes == 0) trace("Boxes are touching each other") 
9 
else if(gap_between_boxes < 0) trace("Boxes are penetrating each other") 
What if the boxes are not oriented nicely?
Although the evaluation of the gap remains the same, we'll have to think of another approach to calculate the length between centers and the halfwidths  this time along the P
axis. This is where vector math comes in handy. We'll project vectors A and B along P to get the halfwidths.
Let's do some math revision.
Vector Math Revision
We'll start by recapping the definition of the dot product between two vectors A
and B
:
We can define the dot product using just the components of the two vectors:
\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
(A_x)(B_x)+(A_y)(B_y)
\]
Alternatively, we can understand the dot product using the magnitudes of the vectors and the angle between them:
\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
A_{magnitude}*B_{magnitude}*cos(theta)
\]
Now, let's try to to figure out the projection of vector A
onto P
.
Referring to the diagram above, we know that the projection value is \(A_{magnitude}*cos(theta)\) (where theta
is the angle between A and P). Although we can go ahead and calculate this angle to obtain the projection, it's tricky. We need a more direct approach:
\[
A. P=A_{magnitude}*P_{magnitude}*cos(theta)\\
A.\frac{P}{P_{magnitude}}=A_{magnitude}*cos(theta)\\
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]
Note that \(\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}\) is actually the unit vector of P.
Now, instead of using the right side of the equation, as we were, we can opt for the left side and still arrive at the same result.
Application to a Scenario
Before we proceed, i'd like to clarify the naming convention used to denote the four corners of both boxes. This will be reflected in the code later:
Our scenario is as below:
Let's say both boxes are oriented 45° from the horizontal axis. We must calculate the following lengths in order to determine the gap between the boxes.
 Projection of A on axis P
 Projection of B on axis P
 Projection of C on axis P
Take special note of the arrows' directions. While projection of A and C onto P will give a positive value, projection of B onto P will actually produce a negative value as the vectors are pointing in opposite directions. This is covered in line 98 of the AS3 implementation below:
1 
var dot10:Point = box1.getDot(0); 
2 
var dot11:Point = box1.getDot(1); 
3 

4 
var dot20:Point = box2.getDot(0); 
5 
var dot24:Point = box2.getDot(4); 
6 

7 
//Actual calculations

8 
var axis:Vector2d = new Vector2d(1, 1).unitVector; 
9 
var C:Vector2d = new Vector2d( 
10 
dot20.x  dot10.x, 
11 
dot20.y  dot10.y 
12 
)

13 
var A:Vector2d = new Vector2d( 
14 
dot11.x  dot10.x, 
15 
dot11.y  dot10.y 
16 
)

17 
var B:Vector2d = new Vector2d( 
18 
dot24.x  dot20.x, 
19 
dot24.y  dot20.y 
20 
)

21 
var projC:Number = C.dotProduct(axis) 
22 
var projA:Number = A.dotProduct(axis); 
23 
var projB:Number = B.dotProduct(axis); 
24 

25 
var gap:Number = projC  projA + projB; //projB is expected to be a negative value 
26 
if (gap > 0) t.text = "There's a gap between both boxes" 
27 
else if (gap > 0) t.text = "Boxes are touching each other" 
28 
else t.text = "Penetration had happened." 
Here's a demo using the above code. Click and drag the red middle dot of both boxes and see the interactive feedback.
For the full source, check out DemoSAT1.as
in the source download.
The Flaws
Well, we can go with the above implementation. But there are a few problems  let me point them out:
First, vectors A and B are fixed. So when you swap the positions of box1
and box2
, the collision detection fails.
Second, we only evaluate the gap along one axis, so situations like the one below will not be evaluated correctly:
Although the previous demo is flawed, we did learn from it the concept of projection. Next, let's improve on it.
Solving the First Flaw
So first of all, we'll need to get the minimum and maximum projections of corners (specifically the vectors from the origin to the boxes' corners) onto P.
The diagram above shows the projection of the minimum and maximum corners onto P when the boxes are oriented nicely along P.
But what if box1
and box2
are not oriented accordingly?
The diagram above shows boxes which are not neatly oriented along P, and their corresponding minmax projections. In this situation, we'll have to loop through each corner of each box and select the correct ones as appropriate.
Now that we have the minmax projections, we'll evaluate whether the boxes are colliding with each other. How?
By observing the diagram above, we can clearly see the geometrical representation for projection of box1.max
and box2.min
onto axis P.
As you can see, when the's a gap between the two boxes, box2.minbox1.max
will be more than zero  or in other words, box2.min > box1.max
. When the position of the boxes are swapped, then box1.min > box2.max
implies there's a gap between them.
Translating this conclusion into code, we get:
1 
//SAT: Pseudocode to evaluate the separation of box1 and box2

2 
if(box2.min>box1.max  box1.min>box2.max){ 
3 
trace("collision along axis P happened") 
4 
}

5 
else{ 
6 
trace("no collision along axis P") 
7 
}

Initial Code
Let's look at some more detailed code for figuring this out. Note that the AS3 code here is not optimised. Although it's long and descriptive, the advantage is that you can see how the math behind it works.
First of all, we need to prepare the vectors:
1 
//preparing the vectors from origin to points

2 
//since origin is (0,0), we can conveniently take the coordinates

3 
//to form vectors

4 
var axis:Vector2d = new Vector2d(1, 1).unitVector; 
5 
var vecs_box1:Vector.<Vector2d> = new Vector.<Vector2d>; 
6 
var vecs_box2:Vector.<Vector2d> = new Vector.<Vector2d>; 
7 

8 
for (var i:int = 0; i < 5; i++) { 
9 
var corner_box1:Point = box1.getDot(i) 
10 
var corner_box2:Point = box2.getDot(i) 
11 

12 
vecs_box1.push(new Vector2d(corner_box1.x, corner_box1.y)); 
13 
vecs_box2.push(new Vector2d(corner_box2.x, corner_box2.y)); 
14 
}

Next, we obtain the minmax projection on box1
. You can see a similar approach used on box2
:
1 
//setting min max for box1

2 
var min_proj_box1:Number = vecs_box1[1].dotProduct(axis); 
3 
var min_dot_box1:int = 1; 
4 
var max_proj_box1:Number = vecs_box1[1].dotProduct(axis); 
5 
var max_dot_box1:int = 1; 
6 

7 
for (var j:int = 2; j < vecs_box1.length; j++) 
8 
{

9 
var curr_proj1:Number = vecs_box1[j].dotProduct(axis) 
10 
//select the maximum projection on axis to corresponding box corners

11 
if (min_proj_box1 > curr_proj1) { 
12 
min_proj_box1 = curr_proj1 
13 
min_dot_box1 = j 
14 
}

15 
//select the minimum projection on axis to corresponding box corners

16 
if (curr_proj1> max_proj_box1) { 
17 
max_proj_box1 = curr_proj1 
18 
max_dot_box1 = j 
19 
}

20 
}

Finally, we evaluate whether there's a collision on that specific axis, P:
1 
var isSeparated:Boolean = max_proj_box2 < min_proj_box1  max_proj_box1 < min_proj_box2 
2 
if (isSeparated) t.text = "There's a gap between both boxes" 
3 
else t.text = "No gap calculated." 
Here's a demo of the implementation above:
You may drag either box around via its middle point, and rotate it with the R and T keys. The red dot indicates the maximum corner for a box, while yellow indicates the minimum. If a box is aligned with P, you may find that these dots flicker as you drag, as those two corners share the same characteristics.
Check out the full source in DemoSAT2.as
in the source download.
Optimisation
If you'd like to speed up the process, there's no need to calculate for the unit vector of P. You can therefore skip quite a number of expensive Pythagoras's theorem calculations which involve Math.sqrt()
:
\[ \begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]
The reasoning is as follows (refer to diagram above for some visual guidance on variables):
1 
/*

2 
Let:

3 
P_unit be the unit vector for P,

4 
P_mag be P's magnitude,

5 
v1_mag be v1's magnitude,

6 
v2_mag be v2's magnitude,

7 
theta_1 be the angle between v1 and P,

8 
theta_2 be the angle between v2 and P,

9 

10 
Then:

11 
box1.max < box2.min

12 
=> v1.dotProduct(P_unit) < v2.dotProduct(P_unit)

13 
=> v1_mag*cos(theta_1) < v2_mag*cos(theta_2)

14 
*/

Now, mathematically, the sign of inequality remains the same if both sides of the inequality are multiplied by the same number, A:
1 
/*

2 
So:

3 
A*v1_mag*cos(theta_1) < A*v2_mag*cos(theta_2)

4 

5 
If A is P_mag, then:

6 
P_mag*v1_mag*cos(theta_1) < P_mag*v2_mag*cos(theta_2)

7 
...which is equivalent to saying:

8 
v1.dotProduct(P) < v2.dotProduct(P)

9 
*/

So whether it's a unit vector or not doesn't actually matter  the result is the same.
Do bear in mind that this approach is useful if you are checking for overlap only. To find the exact penetration length of box1
and box2
(which for most games you'll probably need to), you still need to calculate the unit vector of P.
Solving the Second Flaw
So we solved the issue for one axis, but that's not the end of it. We still need to tackle other axes  but which?
The analysis for boxes is quite straightforward: we compare two axes P and Q. In order to confirm a collision, overlapping on all axes has to be true  if there's any axis without an overlap, we can conclude that there's no collision.
What if the boxes are oriented differently?
Click the green button to turn to another page. So of the P, Q, R, and S axes, there's only one axis that shows no overlapping between boxes, and our conclusion is that there's no collision between the boxes.
But the question is, how do we decide which axes to check for overlapping? Well, we take the normals of the polygons.
In a generalised form, with two boxes, we'll have to check along eight axes: n0
, n1
, n2
and n3
for each of box1
and box2
. However, we can see that the following lie on the same axes:

n0
andn2
ofbox1

n1
andn3
ofbox1

n0
andn2
ofbox2

n1
andn3
ofbox2
So we don't need to go through all eight; just four will do. And if box1
and box2
share the same orientation, we can further reduce to only evaluate two axes.
What about for other polygons?
Unfortunately, for the triangle and pentagon above there's no such shortcut, so we'll have to run checks along all normals.
Calculating Normals
Each surface has two normals:
The diagram above shows the left and right normal of P. Note the switched components of the vector and the sign for each.
For my implementation, I'm using a clockwise convention, so I use the left normals. Below is an extract of SimpleSquare.as
demonstrating this.
1 
public function getNorm():Vector.<Vector2d> { 
2 
var normals:Vector.<Vector2d> = new Vector.<Vector2d> 
3 
for (var i:int = 1; i < dots.length1; i++) 
4 
{

5 
var currentNormal:Vector2d = new Vector2d( 
6 
dots[i + 1].x  dots[i].x, 
7 
dots[i + 1].y  dots[i].y 
8 
).normL //left normals 
9 
normals.push(currentNormal); 
10 
}

11 
normals.push( 
12 
new Vector2d( 
13 
dots[1].x  dots[dots.length1].x, 
14 
dots[1].y  dots[dots.length1].y 
15 
).normL 
16 
)

17 
return normals; 
18 
}

New Implementation
I'm sure you can find a way to optimise the following code. But just so that we all get a clear idea of what's happening, I've written everything out in full:
1 
//results of P, Q

2 
var result_P1:Object = getMinMax(vecs_box1, normals_box1[1]); 
3 
var result_P2:Object = getMinMax(vecs_box2, normals_box1[1]); 
4 
var result_Q1:Object = getMinMax(vecs_box1, normals_box1[0]); 
5 
var result_Q2:Object = getMinMax(vecs_box2, normals_box1[0]); 
6 

7 
//results of R, S

8 
var result_R1:Object = getMinMax(vecs_box1, normals_box2[1]); 
9 
var result_R2:Object = getMinMax(vecs_box2, normals_box2[1]); 
10 
var result_S1:Object = getMinMax(vecs_box1, normals_box2[0]); 
11 
var result_S2:Object = getMinMax(vecs_box2, normals_box2[0]); 
12 

13 
var separate_P:Boolean = result_P1.max_proj < result_P2.min_proj  
14 
result_P2.max_proj < result_P1.min_proj 
15 
var separate_Q:Boolean = result_Q1.max_proj < result_Q2.min_proj  
16 
result_Q2.max_proj < result_Q1.min_proj 
17 
var separate_R:Boolean = result_R1.max_proj < result_R2.min_proj  
18 
result_R2.max_proj < result_R1.min_proj 
19 
var separate_S:Boolean = result_S1.max_proj < result_S2.min_proj  
20 
result_S2.max_proj < result_S1.min_proj 
21 

22 
//var isSeparated:Boolean = separate_p  separate_Q  separate_R  separate_S

23 
if (isSeparated) t.text = "Separated boxes" 
24 
else t.text = "Collided boxes." 
You'll see that some of the variables aren't necessarily calculated to reach the result. If any one of separate_P, separate_Q, separate_R
and separate_S
is true, then they are separated and there's no need to even proceed.
This means we can save a fair amount of evaluation, just by checking each of those Booleans after they've been calculated. It would require rewriting the code, but I think you can work your way through it (or check out the commented block in DemoSAT3.as
).
Here's a demo of the above implementation. Click and drag the boxes via their middle dots, and use the R and T keys to rotate the boxes:
Afterthoughts
When this algorithm is run, it checks through the normal axes for overlappings. I have two observations here to point out:
 SAT is optimistic that there'll be no collision between polygons. The algorithm can exit and happily conclude "no collision" once any axis shows no overlapping. If there were any collision, SAT will have to run through all the axes to reach that conclusion  thus, the more collisions there actually are, the worse the algorithm performs.
 SAT uses the normal of each of the polygons' edges. So the more complex the polygons are, the more expensive SAT will become.
HexagonTriangle Collision Detection
Here's another sample code snippet to check for a collision between a hexagon and a triangle:
1 
private function refresh():void { 
2 
//prepare the normals

3 
var normals_hex:Vector.<Vector2d> = hex.getNorm(); 
4 
var normals_tri:Vector.<Vector2d> = tri.getNorm(); 
5 

6 
var vecs_hex:Vector.<Vector2d> = prepareVector(hex); 
7 
var vecs_tri:Vector.<Vector2d> = prepareVector(tri); 
8 
var isSeparated:Boolean = false; 
9 

10 
//use hexagon's normals to evaluate

11 
for (var i:int = 0; i < normals_hex.length; i++) 
12 
{

13 
var result_box1:Object = getMinMax(vecs_hex, normals_hex[i]); 
14 
var result_box2:Object = getMinMax(vecs_tri, normals_hex[i]); 
15 

16 
isSeparated = result_box1.max_proj < result_box2.min_proj  result_box2.max_proj < result_box1.min_proj 
17 
if (isSeparated) break; 
18 
}

19 
//use triangle's normals to evaluate

20 
if (!isSeparated) { 
21 
for (var j:int = 1; j < normals_tri.length; j++) 
22 
{

23 
var result_P1:Object = getMinMax(vecs_hex, normals_tri[j]); 
24 
var result_P2:Object = getMinMax(vecs_tri, normals_tri[j]); 
25 

26 
isSeparated = result_P1.max_proj < result_P2.min_proj  result_P2.max_proj < result_P1.min_proj 
27 
if (isSeparated) break; 
28 
}

29 
}

30 

31 
if (isSeparated) t.text = "Separated boxes" 
32 
else t.text = "Collided boxes." 
33 
}

For the full code, check out DemoSAT4.as
in the source download.
The demo is below. Interaction is the same as in previous demos: drag via the middle points, and use R and T to rotate.
BoxCircle Collision Detection
Collision with a circle may be one of the simpler ones. Because its projection is the same in all directions (it's simply the circle's radius), we can just do the following:
1 
private function refresh():void { 
2 
//prepare the vectors

3 
var v:Vector2d; 
4 
var current_box_corner:Point; 
5 
var center_box:Point = box1.getDot(0); 
6 

7 
var max:Number = Number.NEGATIVE_INFINITY; 
8 
var box2circle:Vector2d = new Vector2d(c.x  center_box.x, c.y  center_box.y) 
9 
var box2circle_normalised:Vector2d = box2circle.unitVector 
10 

11 
//get the maximum

12 
for (var i:int = 1; i < 5; i++) 
13 
{

14 
current_box_corner = box1.getDot(i) 
15 
v = new Vector2d( 
16 
current_box_corner.x  center_box.x , 
17 
current_box_corner.y  center_box.y); 
18 
var current_proj:Number = v.dotProduct(box2circle_normalised) 
19 

20 
if (max < current_proj) max = current_proj; 
21 
}

22 
if (box2circle.magnitude  max  c.radius > 0 && box2circle.magnitude > 0) t.text = "No Collision" 
23 
else t.text = "Collision" 
24 
}

Check out the full source in DemoSAT5.as
. Drag either the circle or box to see them collide.
Conclusion
Well, that's it for now. Thanks for reading and do leave your feedback with a comment or question. See you next tutorial!