Return to Answer

Our new, better algorithm that uses intersections to detect collisions, but still not as good as the separating axis theorem for telling whether a collision happens##

Our new, better algorithm that uses intersections to help detect collisions, but still not as good as the separating axis theorem for actually telling whether a collision happens##

First of all, in the case of axis-aligned rectangles, Kevin Reid's answer is the best and the algorithm is the fastest. Now, to a more general answer:

You only have to even do all this if it is possible that the bounding circle of A meet that of B. We see here that it won't, and the way to tell the computer that is to compute the distance from C_B to I as in the following picture and make sure it's bigger than the sum of the radii of A and B. If it's bigger, no collision. If it's smaller, then collision.

This doesn't work very well with shapes that are rather long, but in the case of squares or other such shapes, it's a very good heuristic to rule out collision.

To apply this idea more generally and be able to deal with all kinds of shapes and not just those that fit their bounding circle, the radii method doesn't work. You must find the vertex in A that is farthest from the (C_A, C'_A) line on B's side of it (i.e. which maximizes a dot product, let's call the maximum distance d_A), find the vertex in B that is the furthest towards that line (by maximizing a dot product again, let's call the maximum distance d_B) a make sure that d_A + d_B < IC_B.

That's the equivalent of separating B and the swept volume of A with an axis, meaning they won't collide, but that's much more computationally intensive than the radii method (linear time against a small, constant time).

Our new, better algorithm

boolean mayCollide(Body A, Body B) { Vector2D relativeVelocity = A.velocity - B.velocity; if (separatingAxis(A, B, relativeVelocity)) { return false; // there is a separating axis between them } Volume sweptA = sweptVolume(A, relativeVelocity); return contains(minkowskiMinus(sweptA, B), Vector2D(0,0)); } boolean separatingAxis(A, B, relativeVelocity)) { // whatever method you prefer, see google for the code } SetOfVertices minkowskiMinus(Body X, Body Y) { SetOfVertices result = new SetOfVertices(); for (Vertice x in X) { for (Vertice y in Y) { result.addVertice(x-y); } } return result; } 

First of all, in the case of axis-aligned rectangles, Kevin Reid's answer is the best and the algorithm is the fastest.

Second, for simple shapes, use relative velocities (as seen below) and the separating axis theorem for collision detection. It will tell you whether a collision happens in the case of linear motion (no rotation). And if there's rotation, you need a small timestep for it to be precise. Now, to answer the question:

A collision can occur only if it is possible that the bounding circle of A meet that of B. We see here that it won't, and the way to tell the computer that is to compute the distance from C_B to I as in the following picture and make sure it's bigger than the sum of the radii of A and B. If it's bigger, no collision. If it's smaller, then collision.

This doesn't work very well with shapes that are rather long, but in the case of squares or other such shapes, it's a very good heuristic to rule out collision.

The separating axis theorem applied to B and the volume swept by A, however, does tell you whether the collision happens. The complexity of the associated algorithm is linear with the sum of the numbers of vertices of each convex shape, but it is less magical when comes the time to actually handle the collision.

Our new, better algorithm that uses intersections to detect collisions, but still not as good as the separating axis theorem for telling whether a collision happens##

boolean mayCollide(Body A, Body B) { Vector2D relativeVelocity = A.velocity - B.velocity; if (radiiHeuristic(A, B, relativeVelocity)) { return false; // there is a separating axis between them } Volume sweptA = sweptVolume(A, relativeVelocity); return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0)); } boolean radiiHeuristic(A, B, relativeVelocity)) { // the code here } Volume convexHull(SetOfVertices s) { // the code here } boolean contains(Volume v, Vector2D p) {  // the code here } SetOfVertices minkowskiMinus(Body X, Body Y) { SetOfVertices result = new SetOfVertices(); for (Vertice x in X) { for (Vertice y in Y) { result.addVertice(x-y); } } return result; } 

The Minkowski sum of X and Y is the set of all x + y for x ∈ X and y ∈ Y. Supposing (-Y) is the set of all -y for y ∈ Y, then given the previous paragraph, X and Y intersect if and only if X + (-Y) contains 0, that is, the origin.

The Minkowski sum of X and Y is the set of all x + y for x ∈ X and y ∈ Y.

An example for X and Y

X, Y and their Minkowski sum, X+Y

Supposing (-Y) is the set of all -y for y ∈ Y, then given the previous paragraph, X and Y intersect if and only if X + (-Y) contains 0, that is, the origin.

The convex hull of X+Y. We have removed the "inside" vertices.