What is the fastest way to work out 2D bounding box intersection?

Question

Assume that each Box object has the properties x, y, width, height and have their origin at their center, and that neither the objects nor the bounding boxes rotate.

Answer 1

When you ask this question, you'll surely need to test other types of intersections in the future ;). Therefore I suggest THE LIST about Object/Object intersection.

The table provides intersections between all popular object types (boxes, spheres, triangles, cyclinders, cones, ...) in static as well as dynamic situations.

Answer 2

(C-ish pseudocode - adapt language optimizations as appropriate)

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));
}

In English: On each axis, check to see if the centers of the boxes are close enough that they'll intersect. If they intersect on both axes, then the boxes intersect. If they don't, then they don't.

You can change the <'s to <= if you want to count edge-touching as intersecting. If you want a specific edge-touch-only formula, you can't use == - that will tell you if the corners touch, not if the edges touch. You'd want to do something logically equivalent to return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

It's worth mentioning that you can get a small but significant speed increase by storing the half-width and half-height in addition to (or instead of) the full width and full height. On the other hand, it's rare for 2d bounding box intersection to be the performance bottleneck.

Answer 3

This works for two rectangles aligned with the X and Y axis.
Each rectangle has the properties:
"left", the x coordinate of it's left side,
"top", the y coordinate of it's top side,
"right", the x coordinate of it's right side,
"bottom", the y coordinate of it's bottom side,

function IntersectRect(r1:Rectangle, r2:Rectangle):Boolean {
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top);
}

I found the original function here: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect-each-other-or-not/
A description of how it works can also be found there.

Answer 4

If you want object-aligned bounding boxes, try this tutorial on the seperation axis theorem by metanet: http://www.metanetsoftware.com/technique/tutorialA.html

SAT isn't the fastest solution, but it's relatively simple. You're trying to find a single line (or a plane if 3D) that will seperate your objects. If this line exists it's guarenteed to be paralell to the edge of one of your boxes, so you iterate through all edges testing to see if it seperates the boxes.

This also works for axis-aligned boxes by constraining to just the x/y axis.

Answer 5

Actually that arithmetic works fine either way. You can do any arithmetic operation to either side of the < and it doesn't change it (multiplication by a negative means you have to change the less than, though). In that example, the boxes shouldn't collide. If the center of box A is at 1, it spans from -4 to 6. Box b centers at 10, and spans 7.5 to 12.5, there is no collision there...

Now, the method that Wallacoloo posted is not only correct, but will run faster on languages that implement short circuiting, since most checks will return false anyway, the short circuiting can cut out after a single operation, whereas the arithmetic version can only cut out after two arithmetic, one abs, and a less than operation.

Answer 6

The DoBoxesIntersect above is a good pairwise solution. However, if you have a lot of boxes, you still have an O(N^2) problem, and you might find you need to do something on top of that like what Kaj refers to. (In the 3D collision detection literature, this is known as having both a broad-phase and a narrow-phase algorithm. We'll do something really fast to find all possible pairs of overlaps, and then something more expensive to see if our possible pairs are actual pairs.)

The broad-phase algorithm I've used before is "sweep-and-prune"; for 2D, you'd maintain two sorted lists of the start and end of each box. As long as box movement is not >> box scale from frame to frame, the order of these lists isn't going to change much, and so you can use bubble or insertion sort to maintain it. The book "Real-Time Rendering" has a nice writeup on optimizations you can do, but it boils down to O(N+K) time in the broad phase, for N boxes, K of which overlap, and with excellent real-world performance if you can afford N^2 booleans to keep track of which pairs of boxes are intersecting from frame-to-frame. You then have O(N+K^2) time overall, which is << O(N^2) if you have many boxes but only a few overlaps.

Answer 7

Alternate version of ZorbaTHut's answer:

bool DoBoxesIntersect(Box a, Box b) {
     return (abs(a.x - b.x) < (a.width + b.width) / 2) &&
     (abs(a.y - b.y) < (a.height + b.height) / 2);
}

Answer 8

Edit: ZorbaTHut is actually correct I just didn't pay enough attention to his answer. I was assuming that x was the left side of the box rather than the center.

The answer that ZorbaTHut gave is incorrect. Take this example, and to simplify it just looking at the x-axis:

a.x = 1 b.x = 10 a.width = 10 b.width = 5

abs(a.x - b.x) * 2 = 18 (a.width + b.width) = 15

Since (18 < 15) is false the intersection won't be detected.

The answer that Wallacoloo gave looks correct though.

(btw, I wanted to post this as a comment to Zorbas answer but I couldn't see how).

Answer 9

Depending on the problem you try to solve you might be better off keeping track of your object while you move them, ie, keep a list of sorted x start and end positions and one for start and end y positions. If you have to do a LOT of overlap checks and therefore need to optimize, you can use this to your advantage, as you can immediately look up who is ending closes to your left, everyone who's ending is to the left of that can be pruned immediately. Same apply for top, bottom and right.
The bookkeeping costs time of course, so it's more suited for a situation with few moving objects but lots of overlap checks.
Another optionh is spatial hashing, where you bucket the objects based on approximate position (size might put em in multiple buckets), but there again, only if there's a lot of objects, with relatively few of them moving per iteration due to bookkeeping cost.
Basically anything that avoids (n*n)/2 (if you check object a against b you won't have to check b against a obviously) helps more than optimizing bounding box checks. If bounding box checks are a bottleneck, I'd seriously advise to look into alternative solutions to the problem.

Answer 10

The distance between centers is not the same as the distance between corners (when one box is inside the other for instance), so IN GENERAL, this solution is the correct one (me thinks).

distance between centers (for, say, x): abs(x1+1/2*w1 - x2+1/2*w2) or 1/2 * abs(2*(x1-x2)+(w1-w2)

Minimum distance is 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). the halves cancel so..

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));