math - Separating Axis Theorem and Python

Question

This is what I am currently doing:

Creating 4 axis that are perpendicular to 4 edges of 2 rectangles. Since they are rectangles I do not need to generate an axis (normal) per edge.

I then loop over my 4 axes.

So for each axis: I get the projection of every corner of a rectangle on to the axis. There are 2 lists (arrays) containing those projections. One for each rectangle. I then get the dot product of each projection and the axis. This returns a scalar value that can be used to to determine the min and max.

Now the 2 lists contain scalars and not vectors. I sort the lists so I can easily select the min and max values. If the min of box B >= the max of box A OR the max of box B <= the min of box A then there is no collision on that axis and no collision between the objects.

At this point the function finishes and the loop breaks.

If those conditions are never met for all the axis then we have a collision

I hope this was the correct way of doing it.

The python code itself can be found here http://pastebin.com/vNFP3mAb

Also: http://www.gamedev.net/page/reference/index.html/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604

The problem i was having is that the code above does not work. It always detects a a collision even where there is not a collision. What i typed out is exactly what the code is doing. If I am missing any steps or just not understanding how SAT works please let me know.

Answer 1

In general it is necessary to carry out the steps outlined in the Question to determine if the rectangles "collide" (intersect), noting as the OP does that we can break (with a conclusion of non-intersection) as soon as a separating axis is found.

There are a couple of simple ways to "optimize" in the sense of providing chances for earlier exits. The practical value of these depends on the distribution of rectangles being checked, but both are easily incorporated in the existing framework.

(1) Bounding Circle Check

One quick way to prove non-intersection is by showing the bounding circles of the two rectangles do not intersect. The bounding circle of a rectangle shares its center, the midpoint of either diagonal, and has diameter equal to the length of either diagonal. If the distance between the two centers exceeds the sum of the two circles' radii, then the circles do not intersect. Thus the rectangles also cannot intersect. If the purpose was to find an axis of separation, we haven't accomplished that yet. However if we only want to know if the rectangles "collide", this allows an early exit.

(2) Vertex of one rectangle inside the other

The projection of a vertex of one rectangle on axes parallel to the other rectangle's edges provides enough information to detect when that vertex is inside the other rectangle. This check is especially easy when the latter rectangle has been translated and unrotated to the origin (with edges parallel to the ordinary axes). If it happens that a vertex of one rectangle is inside the other, the rectangles obviously intersect. Of course this is a sufficient condition for intersection, not a necessary one. But it allows for an early exit with a conclusion of intersection (and of course without finding an axis of separation because none will exist).