A collision detection algorithm for moving rectangles
This algorithm determines if two moving rectangles have collided and the coordinates of the respective rectangles at the point of collision.
We want to know if two rectangles, A and B, have collided over a particular interval. A naive approach would simply check for the intersection of the two rectangles at the end of the interval (see fig. 1). Unfortunately this misses cases where the rectangles have passed entirely through each other and come out the other side (see fig. 2). Intersection is therefore not strong enough for collision detection. Checking for intersection will also not tell us the point of collision, only that the rectangles have collided.
Figure 1 – B intersects A.
Figure 2 – B has passed entirely through A and does not intersect it in the final position.
The Cohen-Sutherland algorithm can be used to decide if a line intersects a rectangle. The same basic procedure can be used to decide if the paths of two rectangles intersect. If they don’t intersect then we can be sure no collision has occurred (see fig. 3). If they do intersect we need to determine if the two rectangles ever come into contact (see fig. 4).
Figure 3 – the paths of A and B do not intersect.
Figure 4 – the paths of A and B intersect.
The paths of two rectangles, A and B, do not intersect (and therefore have not collided) if B remains on the same side of A. We say B is to the left of A if and only if the right side of B is to the left of the left side of A (fig. 5 but not fig. 6), and similarly for the other edges. Therefore the rectangles in fig. 3 have not collided because B is below A initially, and remains so.
Figure 5 – B is entirely to the left of A.
Figure 6 – B is entirely below A but no longer entirely to the left.
The converse is not true, if B moves from one side of A to another, it does not necessarily follow that the rectangles have collided. In both fig. 7 and fig. 8, B is initially to the left of A, and finishes below and to the right of A. However, B does not collide with A in fig. 7, but does in fig. 8.
Figure 7 – B is initially to the left of A and finishes below and to the right of A but does not collide with A.
Figure 8 – B is initially to the left of A and finishes below and to the right of A, colliding with A along the way.
To work out whether A and B actually collide we calculate the position of the two rectangles where the edges of A and B are collinear. If B has moved from one side of A to another at this point then it has already passed A and the two rectangles have not collided. In fig. 9, B is not initially below A, but when the left edge of A and the right edge of B are collinear it is, so A and B do not collide. On the other hand, in fig. 8 B is not completely below A when the two edges are collinear so A and B have collided.
Figure 9 – B is below A when the left edge of A is collinear with the right edge of A so A and B do not collide.
Pseudo-code:
out0 = outcode(a0, b0)
out1 = outcode(a1, b1)
if (out0 == 0 && out1 == 0) then the rectangles are intersecting initially
if ((out0 & out1) != 0) then no collision has occurred
c = 0
if ((out1 & LEFT) != 0) {
c’ = (a0.x0 – b0.x1) / ((b1.x1 – b0.x1) – (a1.x0 – a0.x0))
if c’ > c then c = c’
}
if ((out1 & TOP) != 0) {
c’ = (a0.x0 – b0.x1) / ((b1.x1 – b0.x1) – (a1.x0 – a0.x0))
if c’ > c then c = c’
}
if ((out1 & RIGHT) != 0) {
c’ = (a0.x0 – b0.x1) / ((b1.x1 – b0.x1) – (a1.x0 – a0.x0))
if c’ > c then c = c’
}
if ((out1 & BOTTOM) != 0) {
c’ = (a0.x0 – b0.x1) / ((b1.x1 – b0.x1) – (a1.x0 – a0.x0))
if c’ > c then c = c’
}
ac.x0 = a0.x0 + c.(a1.x0 – a0.x0)
ac.x1 = a0.x1 + c.(a1.x1 – a0.x1)
ac.y0 = a0.y0 + c.(a1.y0 – a0.y0)
ac.y1 = a0.y1 + c.(a1.y1 – a0.y1)
bc.x0 = b0.x0 + c.(b1.x0 – b0.x0)
bc.x1 = b0.x1 + c.(b1.x1 – b0.x1)
bc.y0 = b0.y0 + c.(b1.y0 – b0.y0)
bc.y1 = b0.y1 + c.(b1.y1 – b0.y1)
outc = outcode(ac, bc)
if ((outc & ~out0) != 0) then no collision has occurred
else a collision has occurred at point c
Is it possible to work out when the edges of A and B are collinear without simulating the movement in full?
I tried writing a simulation, but it suffers from a lack of resolution, so for those “close calls”, it may get it wrong. I may be doing the simulation wrong. Here is what I’m doing in some random pseudocode:
Vector movementVectorA = (endPointA – startPointA) / 100
Vector movementVectorB = (endPointB – startPointB) / 100
for( i
Yes it is possible. In figs. 8 and 9 above we know if a collision occurred it occurred between the right edge of B and the left edge of A. The edges are coolinear when their x coordinates are the same.
So:
1. axc = bxc
where c denotes the point of collision.
Now:
2. axd = ax0 + d.(ax1 – ax0)
where 0 denotes the initial position and 1 the endpoint.
Similarly for b.
So from 1 and 2:
3. ax0 + c.(ax1 – ax0) = bx0 + c.(bx1 – bx0)
=> c.(ax1 – ax0) – c.(bx1 – bx0) = bx0 – ax0
=> c.((ax1 – ax0)) – (bx1 – bx0)) = bx0 – ax0
=> c = (bx0 – ax0) / ((ax1 – ax0) – (bx1 – bx0))
I’ve added some psuedocode to the post.