It would appear that I've made an error

Back in 2011 I implemented the Separating Axis Theorem in JavaScript to help detect polygon collisions in HTML5 games. Now that I've started implementing similar games in Java to play on my OUYA, it has come to my attention that my algorithm had a slight mistake in it.

The problem had to do with calculating the Minimum Translation Vector, which tells you how to move one of the polygons to get them out of collision. If you were just using the algorithm to detect collision with a true/false you wouldn't notice any problem.

Here's what I did wrong...

After projecting both shapes' vertices onto the normal axis, you will have two line segments and you are supposed to determine how big the overlap (if any) is between the them. You can read a great explanation of the whole algorithm on the Code Zealot blog.

So let's say you end up with two line segments, A and B. Both sit on the X axis, so you can ignore any Y value. A runs from 1.5 to 4.4 while B runs from -2.8 to 2. What would you say the overlap is? The correct answer would be 0.5, but my implementation of the algorithm was coming up with 7.2.

Here was my calculation of the overlap:

o = (maxA > minB ? maxA - minB : maxB - minA);

See anything wrong there? In the case I outlined above, maxA was 4.4, obviously greater than minB which was -2.8. So I calculated the overlap as 4.4 + 2.8. Wrong! What was I thinking? Try it yourself with other line segments...you'll see that it sometimes gives you a correct value but often does not. If only I had created a good unit test for this code years ago. Fortunately, I did create such a test for my Java version using JUnit, and found my mistake. Here is the correct calculation of overlap:

o = (maxA > maxB ? maxB - minA : maxA - minB);

I've updated my JavaScript version, so people who find it on my previous blog entry won't be led astray. Sorry about that. I'll post my Java version soon, along with what is (hopefully) a good explanation of how it works.