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:
How to tell in the general case whether two convex shapes intersect?
I'll give you an algorithm that works for all convex shapes and not just hexagons.
Suppose X and Y are two convex shapes. They intersect if and only if they have a point in common, i.e. there is a point x ∈ X and a point y ∈ Y such that x = y. If you regard the space as a vector space, then this amounts to saying x - y = 0. And now we get to this Minkowski business:
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.
Side remark: why do I write X + (-Y) instead of X - Y ? Well, because in mathematics, there is an operation called the Minkowski difference of A and B which is sometimes written X - Y yet has nothing to do with the set of all x - y for x ∈ X and y ∈ Y (the real Minkowski difference is a little more complex).
So we'd like to compute the Minkowski sum of X and -Y and to find whether it contains the origin. The origin is not special compared to any other point, so that to find whether the origin is within a certain domain, we use an algorithm that could tell us whether any given point belongs to that domain.
The Minkowski sum of X and Y has a cool property, which is that if X and Y are convex, then X+Y is too. And finding whether a point belongs to a convex set is much easier than if that set were not (known to be) convex.
We can't possibly compute all of the x - y for x ∈ X and y ∈ Y because there are an infinity of such points x and y, so hopefully, since X, Y and X + Y are convex, we can just use the "outermost" points defining the shapes X and Y, which are their vertices, and we'll get the outermost points of X + Y, and also some more.
These additional points are "surrounded" by the outermost ones of X + Y so that they do not contribute to defining the newly obtained convex shape. We say that they don't define the "convex hull" of the set of points. So what we do is that we get rid of them in preparation for the final algorithm that tells us whether the origin is within the convex hull.
The convex hull of X+Y. We have removed the "inside" vertices.
We therefore get
A first, naive algorithm
boolean intersect(Shape X, Shape Y) {
SetOfVertices minkowski = new SetOfVertices();
for (Vertice x in X) {
for (Vertice y in Y) {
minkowski.addVertice(x-y);
}
}
return contains(convexHull(minkowski), Vector2D(0,0));
}
The loops obviously have complexity O(mn) where m and n are the number of vertices of each shape. The minkoswki set contains mn elements at most. The convexHull algorithm has a complexity that depends on the algorithm you used, and you can aim for O(k log(k)) where k is the size of the set of points, so in our case we get O(mn log(mn)). The contains algorithm has a complexity that is linear with the number of edges (in 2D) or faces (in 3D) of the convex hull, so it really depends on your starting shapes, but it won't be greater than O(mn).
I'll let you google for the contains algorithm for convex shapes, it's a pretty common one. I may put it here if I have the time.
But it's collision detection we're doing, so we can optimize that a lot
We originally had two bodies A and B moving without rotation during a timestep dt (from what I can tell by looking at your pictures). Let's call vA and vB the respective speeds of A and B, which are constant during our timestep of duration dt. We get the following:
and, as you point out in your pictures, these bodies do sweep through areas (or volumes, in 3D) as they move:
and they end up as A' and B' after the timestep.
To apply our naive algorithm here, we would only have to compute the swept volumes. But we're not doing this.
In the reference frame of B, B doesn't move (duh!). And A has a certain velocity with respect to B that you get by computing vA - vB (you can do the converse, compute the relative velocity of B in the reference frame of A).
From left to right: velocities in the base reference frame; relative velocities; computing relative velocities.
By regarding B as immobile in its own reference frame, you only have to compute the volume that A sweeps through as it moves during dt with its relative velocity vA - vB.
This decreases the number of vertices to be used in the Minkowski sum computation (sometimes greatly).
Another possible optimization is at the point where you compute the volume swept by one of the bodies, let's say A. You don't have to translate all of the vertices making up A. Only those that belong to edges (faces in 3D) whose outer normal "face" the direction of the sweeping. Surely you had noticed that already when you computed your swept areas for the squares. You can tell whether a normal is towards the sweeping direction using its dot product with the sweeping direction, which has to be positive.
The last optimization, that has nothing to do with your question regarding intersections, is really useful in our case. It uses those relative velocities we mentioned and the so-called separating axis method. Surely you know about it already.
Suppose you know the radii of A and B with respect to their centers of mass (that is to say, the distance between the center of mass and the vertex farthest from it), like this:
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 CB 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 help detect collisions, but still not as good as the separating axis theorem for actually 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;
}
