63
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Are these axis or object-aligned bounding boxes? \$\endgroup\$ – tenpn Jul 16 '10 at 9:48
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Dave O. Jul 17 '10 at 18:13
  • 2
    \$\begingroup\$ Please rephrase Your question to bounding rects. From my point of view box implies a 3d object. \$\endgroup\$ – Dave O. Jul 17 '10 at 18:16

11 Answers 11

56
\$\begingroup\$

(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.

\$\endgroup\$
  • 9
    \$\begingroup\$ This obviously assumes the boxes are axis-aligned. \$\endgroup\$ – tenpn Jul 16 '10 at 9:48
  • 1
    \$\begingroup\$ Abs shouldn't be particularly slow - no slower than a conditional, at least, and the only way to do it without abs (that I'm aware of) involves extra conditionals. \$\endgroup\$ – ZorbaTHut Jul 16 '10 at 9:51
  • 4
    \$\begingroup\$ Yes, it does assume axis-aligned boxes. The structures as described don't have any way of indicating rotation, though, so I felt it was safe. \$\endgroup\$ – ZorbaTHut Jul 16 '10 at 9:52
  • 3
    \$\begingroup\$ Here are some good tips for speeding up calulations in Actionscript (mainly integer calc): lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math I'm posting this, because it also contains a faster replacement for Math.abs(), which tends to slow down things in Actionscript indeed (speaking of performance critical stuff of course). \$\endgroup\$ – bummzack Jul 16 '10 at 17:32
  • 2
    \$\begingroup\$ You're missing that they have the origin at the center, not at the left edge. A box that runs from 0 to 10 will actually have "x = 5", while a box that runs from 8 to 12 will have "x = 10". You end up with abs(5 - 10) * 2 < (10 + 4) => 10 < 14. You'll need to do some simple tweaking in order to make it work with topleft-corner-and-size. \$\endgroup\$ – ZorbaTHut Aug 15 '15 at 10:13
39
\$\begingroup\$

This works for two rectangles aligned with the X and Y axis.
Each rectangle has the properties:
"left", the x coordinate of its left side,
"top", the y coordinate of its top side,
"right", the x coordinate of its right side,
"bottom", the y coordinate of its 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);
}

Note that this is designed for a coordinate system in which the +y axis points down and the +x axis is directed to the right (i.e. typical screen/pixel coordinates). To adapt this to a typical cartesian system in which +y is directed upward, the comparisons along the vertical axes would be reversed, e.g.:

return !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

The idea is to capture all possible conditions upon which the rectangles will not overlap, and then negate the answer to see if they are overlapped. Regardless of the direction of the axes, it's easy to see that two rectangles will not overlap if:

  • the left edge of r2 is further right than the right edge of r1

     ________     ________
    |        |   |        |
    |   r1   |   |   r2   |
    |        |   |        |
    |________|   |________|
    
  • or the right edge of r2 is further left than the left edge of r1

     ________     ________
    |        |   |        |
    |   r2   |   |   r1   |
    |        |   |        |
    |________|   |________|
    
  • or the top edge of r2 is below the bottom edge of r1

     ________ 
    |        |
    |   r1   |
    |        |
    |________|
     ________ 
    |        |
    |   r2   |
    |        |
    |________|
    
  • or the bottom edge of r2 is above the top edge of r1

     ________ 
    |        |
    |   r2   |
    |        |
    |________|
     ________ 
    |        |
    |   r1   |
    |        |
    |________|
    

The original function - and an alternative description of why it works - can be found here: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect-each-other-or-not/

\$\endgroup\$
  • 1
    \$\begingroup\$ Surprisingly intuitive and shows once more that when finding the answer is too hard, trying to find the answer to an opposite question might help you out. Thanks! \$\endgroup\$ – Lodewijk Jun 26 '14 at 23:05
  • 1
    \$\begingroup\$ You should mention that the y axis points down (as in an image). Otherwise the inequalities r2.top > r1.bottom and r2.bottom < r1.top needs to be reversed. \$\endgroup\$ – user1443778 Jun 3 '15 at 17:12
  • \$\begingroup\$ @user1443778 good catch! I went ahead and loosely explained the logic behind this algorithm in a coordinate system-agnostic way, too. \$\endgroup\$ – Ponkadoodle Jun 4 '15 at 5:15
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I wasn't thinking of rotation, but thanks that's an interesting link. \$\endgroup\$ – Iain Jul 16 '10 at 12:17
6
\$\begingroup\$

Lot of math here for a very simple problem, assume that we have 4 points determined for a rect, top, left, bottom, right...

In the case of determining whether 2 rects collide we need only look that all possible extremes that would prevent collisions, if none of these are met, then the 2 rects MUST collide, if you want to include boundary collisions, simply replace the > and < with appropriate >= and =<.

struct aRect{
  float top;
  float left;
  float bottom;
  float right;
};

bool rectCollision(rect a, rect b)
{
  return ! ( b.left > a.right || b.right < a.left || b.top < a.bottom || b.bottom > a.top);
}
\$\endgroup\$
  • \$\begingroup\$ I'm honestly not sure why this isn't the top-voted answer. It's simple, correct and efficient. \$\endgroup\$ – 3Dave Dec 16 '16 at 19:45
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ 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 s \$\endgroup\$ – Deleter Aug 11 '10 at 17:34
  • \$\begingroup\$ Yes I realised this when I woke up this morning. Chris bambusaled me with his < > mix up. \$\endgroup\$ – Iain Aug 12 '10 at 6:13
  • 1
    \$\begingroup\$ Two problems: first, division tends to be significantly slower than multiplication. Second, if the values involved are integers, this might result in some integer truncation issues (a.x = 0, b.x = 9, a.width = 9, b.width = 10: abs(0-9) < (9+10)/2, 9 < 19/2, 9 < 9, function returns false despite the fact that the boxes definitively intersect.) \$\endgroup\$ – ZorbaTHut Feb 5 '12 at 1:33
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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));
\$\endgroup\$
  • 1
    \$\begingroup\$ What's with the "return" statement in there? \$\endgroup\$ – doppelgreener Sep 23 '12 at 11:36
1
\$\begingroup\$

Here's my implementation in Java assuming a twos-complement architecture. If you're not on twos-complement, use a standard Math.abs function call instead:

boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
    return
        (
            lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
            lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
            lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
        ) == 0;
}

int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
    final int
            leftWidth = leftMax - leftMin,
            rightWidth = rightMax - rightMin,

            leftMid = leftMin + ((leftMax - leftMin) >> 1),
            rightMid = rightMin + ((rightMax - rightMin) >> 1);

    return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
}

int abs(int value) {
    final int mask = value >> (Integer.SIZE - 1);

    value ^= mask;
    value += mask & 1;
    return value;
}

Assuming a half-decent compiler / LLVM inline expands these functions to avoid expensive stack juggling and v-table look-ups. This will fail for input values that are close to 32-bit extremes (i.e. Integer.MAX_VALUE and Integer.MIN_VALUE).

\$\endgroup\$
1
\$\begingroup\$

The fastest way is combine all 4 values in a single vector register.

Store the boxes in a vector with following values [ min.x, min.y, -max.x, -max.y ]. If you store boxes like this, the intersection test only takes 3 CPU instructions:

_mm_shuffle_ps to reorder the second box flipping min and max halves.

_mm_xor_ps with magic number _mm_set1_ps(-0.0f) to flip signs of all 4 values in the second box.

_mm_cmple_ps to compare all 4 values with each other, comparing following two registers:

[ a.min.x, a.min.y, -a.max.x, -a.max.y ] < [ b.max.x, b.max.y, -b.min.x, -b.min.y ]

Finally, if needed, _mm_movemask_ps to get the result out of vector unit into a scalar register. Value 0 means the boxes intersected. Or if you have more than 2 boxes this is not needed, leave the values in vector registers and use bitwise operations to combine results from multiple boxes.

You have not specified language nor platform, but the support for SIMD like this, or very similar, is available in all platform and languages. On mobile, ARM has NEON SIMD with very similar stuff. .NET has Vector128 in System.Runtime.Intrinsics namespace, and so on.

\$\endgroup\$
0
\$\begingroup\$

The term that you are looking for is AABB bounding boxes. If you look at https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection you will see a few examples for intersection testing. The particular code for this is:

function intersect(a, b) {
  return (a.minX <= b.maxX && a.maxX >= b.minX) &&
         (a.minY <= b.maxY && a.maxY >= b.minY);
}

I cannot comment on results in this community yet, but one highly rated answer from @Ponkadoodle is not correct. See below test that shows intersecting rectangles that the algorithm would not detect correctly:

// THIS DOES NOT WORK, its a test to show a false-negative detection.

const r1 = {
  left: 100,
  right: 200,
  top: 200,  
  bottom: 300
};

const r2 = {
  left: 101,
  right: 199,
  top: 51,
  bottom: 201
}

let result = !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

console.log(`Intersects? ${result}`);

New contributor
tseifried is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.