Separating Axis Theorem (SAT) Explanation
Separating Axis Theorem (SAT) is a technique for calculating collisions between convex polygons.
I’m by no means an expert on it, but after the need arose for me to do some collision detection I did a pile of reading and finally got it working in ActionScript 3.
I thought I would share what I learnt in the hope others wouldn’t suffer so much :)
When I found myself in a need to calculate collisions between polygons in flash, I came across a method known as Separating Axis Theorem (SAT). The only problem I had was that I really struggled to get a grasp on it.
After a lot of reading about collision detection, and looking at code samples, it all finally clicked.
To help out the other non-maths minded people I thought I would write this quick explanation to run through the basic principles of how it works. I’ve also included a demo using SAT collision detection, as well as some ActionScript 3 classes you can download and use.
Note: SAT does require a bit of work with vector math, so it may be a good idea to brush up on your vectors before getting too far into SAT.
Interactive Demo
Use your mouse to drag the shapes around. Whilst dragging, use the arrow keys to change the scale and rotation of the shapes. When the two shapes collide they will change colour (red) and show a possible reaction (grey).
The quick rundown
Basically, the goal of SAT (and every other collision detection) is to test and see if is a gap between two shapes. The method that SAT uses is what makes it unique.
The best analogy I have heard for SAT technique is like this:
Imagine taking a torch and shining it on the two shapes you are testing from different angles. What sort of shadows would it cast on the wall behind it?
If you work your way around the shapes and never find a gap in the shadows then the objects must be touching. If you find a gap, then they are clearly not touching.
From a programming point of view it would be too intensive to check every possible angle. Luckily, due to the nature of the polygons, there is only a few key angles you need to check.
The angles you need to check are the same as the sides of the polygons. This means that the maximum number of angles to check is the sum of the number of sides the two shapes you are testing have. Eg. Two pentagons would require ten angles to be checked.
So how do you make it work in code?
It’s a simple but repetitive method, so here is a very basic step by step.
Please Note: that the code samples are just a very rough guide as to how it could be done. For a more complete working sample, check out the (#download) section
Step 1. Take one side from one of the polygons you are testing and find the normal (perpendicular) vector from it. This will be the ‘axis’. It needs to be a unit vector, so when you calculate it, be sure to normalize it. 
Something a bit like:
// points / verts in the geometry. Make sure they are in
let vertices = [ {x:1, y:1}, {x:1, y:-1}, {x:-1, y:-1}, {x:-1, y:1} ];
// get the perpendicular axis - you would need to loop over these...
let axis = {
x: -(vertices.y - vertices.y),
y: vertices.x - vertices.x
}
// be sure to normalize the axis by making it length to 1. You can do that with something like
let magnitude = Math.sqrt(Math.pow(axis.x,2), Math.pow(axis.y, 2));
if (magnitude != 0)
{
axis.x *= 1 / magnitude;
axis.y *= 1 / magnitude;
}
Step 2. Loop through every point on the first polygon and project it onto the axis. (Keep track of the highest and lowest values found for this polygon) 
// helper method for calculating the dot product of a vector
vectorDotProduct(pt1, pt2)
{
return (pt1.x * pt2.x) + (pt1.y * pt2.y);
}
// verts and axis from earlier...
// vertices = [ {x:1, y:1}, {x:1, y:-1}, {x:-1, y:-1}, {x:-1, y:1} ];
// axis = {x:1, y: 0}
// get an initial min/max value. you will need the min max for both shapes
let p1min = vectorDotProduct(axis, vertices);
let p1max = min;
// loop over all the other verts to complete the range
for (let i =1; i < verts.length; i++)
{
let dot = vertices;
p1min = Math.min(p1min , dot);
p1max = Math.max(p1max , dot);
}
Step 3. Do the same for the second polygon. 
Now you will have both sets of vertices projected onto the axis, which is good, but they will probably be overlapping at this point because we haven’t taken into consideration the distance between the two objects. (I forgot about this step until I rewrote the code, hence the picture doesn’t show it…) You can correct for this spacing issue by projecting the distance between the shapes onto the same axis, then adding it to one of the shapes projection. Something kinda like this:
// vector offset between the two shapes
let vOffset = { polygon1.x - polygon2.x, polygon1.y - polygon2.y };
// project that onto the same axis as just used
let sOffset = vectorDotProduct(axis, vOffset);
// that will give you a scaler value that you can add to the min/max of one of the polygons from earlier
p1min += sOffset;
p1max += sOffset;
Step 4. Check the values you found and see if they overlap. 
If you find a gap between the two ‘shadows’ you have projected onto the axis then the shapes must not intersect. However, if there is no gap, then they might be touching and you have to keep checking until you have gone through every side of both polygons. If you get through them all without finding a gap then they collide.
// quick overlap test of the min and max from both polygons
if ( (p1min - p2max > 0) || p2min - p1max > 0) )
{
// there is a gap - bail
return null;
}
That’s basically it.
As an added bonus, if you keep track of which axis has the smallest shadow overlap (and how much of an overlap that was) then you can apply that value to the shapes to separate them.
What about circles?
Testing a circle against a polygon in SAT is a little bit strange but it can be done.
The main thing to note is that a circle does not have any sides so there is no obvious axis that you can test against. There is one ‘not so obvious’ axis you do need to test however. This is the axis that runs from the centre of the circle to the closest vertex on the polygon.
// presume with have some info
vertices = [ {x:1, y:1}, {x:1, y:-1}, {x:-1, y:-1}, {x:-1, y:1} ];
polygonPos = { x:0, y: 0}
circlePos = { x: 5, y:1}
circleRadiuis = 4;
// find the closest by doing a distance check
let minDist = Number.MAX_VALUE;
let closestDelta = null;
let axis = null;
for (let vert in vertices)
{
// make sure you are using the vert in the same space... this will depend on how you have the data set up
let worldVert = { x: polygonPos.x + vert.x, y: polygonPos.y + vert.y }
// delta between the circle and this vert in world space.
let delta= { x: worldVert.x - circlePos.x, y: worldVert.y - circlePos.y }
// use pythagoras theorem to get the distance - you can skip the sqrt because we don't need the true distance in this check
let dist = Math.pow(delta.x, 2) + Math.pow(delta.y, 2));
if (dist < minDist)
{
minDist = dist;
closestDelta = delta;
}
}
// you can now convert the closest delta into a unit vector axis
let magnitude = Math.sqrt(Math.pow(closestDelta.x,2), Math.pow(closestDelta.y, 2));
if (magnitude != 0)
{
axis.x = closestDelta.x * (1 / magnitude);
axis.y = closestDelta.x * (1 / magnitude);
}
After that it is just a matter of going through the usual routine of looping through every axis on the other polygon and checking for overlaps.
Oh, and in case you are wondering how to project a circle onto the axis, you simply project the centre point of the circle and then add and subtract the radius.
// props from earlier
// axis = {x:1, y: 0}
// circleCenter = {x:5, y:1 }
// project the center
let temp = vectorDotProduct(axis, circleCenter );
// calc the range using the radius
let circleMin = temp - circleRadius;
let circleMax = temp + circleRadius;
// Now use this range to do the overlap test described earlier...
Pros and Cons
Like all collision detection techniques, SAT has it’s pro’s and cons. Here is a quick rundown of some of them:
Pros
- It is fast - It uses pretty basic vector math and you can bail out of a test as soon as a gap is detected, eliminating unnecessary calculations.
- It is accurate - at least as far as I can tell.
Cons
- It only works with Convex polygons - complex shapes are out unless you build them out of smaller convex shapes, and then test each individual shape.
- It doesn’t tell you which sides are touching - only how far they are overlapping and the shortest distance to separate them.
There is probably a bunch more but these were the main ones I could think of.
Conclusion
I hope that this has helped to shed some light on the separating axis theorem. I’ve tried to keep it as simple as possible without shedding too much information. (I’m by no means an expert in maths so I apologise if I left anything out)
Here are a few links to other pages that helped me understand SAT collision detection.
- N Tutorials — SAT (archived) - more detailed descriptions and some cool interactive examples. I learnt a lot from this page.
- Building A Physics Engine — Basic Intersection Detection (archived) - good SAT explanation and sample code - I used this as a basis for creating my own code.
- Vector tutorials (archived) - Good resource for learning about Vectors
- SAT collision system forum post (archived) - a SAT collision system a member created - gave me some ideas on how to calculate reactions, etc.
Download
If you want to see the code for my interactive demo, you can grab them from my SAT_JS. It is in no way optimised but should serve as a good example of the above explanation. (The original SAT_AS3 is also available is you are so inclined)
Basically, you create two shapes from the (SATPolygon or SATCircle classes) and then test them with the static ‘SAT.test()’ method. If they touch then a ‘CollisionInfo’ object will be returned. If they don’t touch then it will return ‘null’. The CollisionInfo object has a bunch of information about the collision that can be used to separate the two objects, etc.
The SATDemo class contains all the logic for creating the demo shown earlier in this post.
☕ Buy me a Hot Chocolate