Detecting Whether Two Boxes Overlap

Questions asked on job interviews also make for interesting blog post topics. (And very rarely, they are also practical!) This post discusses one of my favorite interview questions: “How can you tell if two axially-aligned 2D boxes intersect?” The adjective “axially-aligned” means that the sides of the box are parallel to the x- and y-axes; the box is not arbitrarily oriented. The acronym AABB is often used for axially-aligned bounding box.

I like this question because it is both a test of experience and problem solving ability. Entry-level applicants aren’t necessarily expected to know the answer, but they should be able to suggest an approach (with very high frequency they suggest the incorrect solution discussed below), work through some examples, and arrive at the correct one. Most experienced web/GUI programmers have worked with 2D boxes and have encountered the problem, and should know the proper solution. However, they often do not immediately perceive the principle that extends the idea beyond AABB’s to arbitrarily-oriented boxes. In summary, it’s a problem with a deceptively simple starting point and many branching points depending on the skill of the applicant, which is precisely why it’s a great interview question.

Let’s say that we have basic 2D vector and bounding box classes such as:

// Simple 2D vector class
struct Vec2D
{
    float x,y;
};
 
// 2D axially-aligned bounding box.
struct Box2D
{
    Vec2D min, max;
};

So the goal of the question is a function with a prototype such as

bool BoxesIntersect(const Box2D &a, const Box2D &b);

When faced with this problem, inexperienced programmers produce a particular solution that doesn’t work with such regularity, that it is worth mentioning. They suggest to check the four corners of box A, to see if any are containing within box B, and also check B‘s corners to see if they are contained within A. But this approach fails in the following example.

The correct approach is to work by process of elimination. What are some situations when it is clear that the two AABB’s do not intersect? We can immediately think of an obvious case: if box A is completely to the left of B, then the boxes cannot intersect. Likewise if A is completely to the right of B, or above or below it. Are there any other cases to consider? No. If A is completely to the left or right of B, then the vertical positions of the boxes do not matter. If two boxes do not intersect, they will fit into at at least one of the four cases just mentioned. (If you are not convinced of this, a useful exercise is to try to categorize all the possible possible cases.) So the only remaining task is to express “A is completely to the left of B,” and so forth, in C.

This is the correct answer:

bool BoxesIntersect(const Box2D &a, const Box2D &b)
{
    if (a.max.x < b.min.x) return false; // a is left of b
    if (a.min.x > b.max.x) return false; // a is right of b
    if (a.max.y < b.min.y) return false; // a is above b
    if (a.min.y > b.max.y) return false; // a is below b
    return true; // boxes overlap
}

(By the way, whether “<” and “>” should be “<=” and “>=” depends on exactly what you mean by boxes “intersecting.” If you are using floating point coordinates and this distinction matters, you are probably doing something wrong.)

Most everybody understands the solution to this problem, and it extends in a straightforward way into 3D. So that’s pretty much all there is to say about AABB’s.

But what about boxes that are arbitrarily oriented? How about convex polygons (or polyhedra in 3D) with an arbitrary number of sides? To solve these problems requires that we distill from our ad-hoc solution a more fundamental principle, known as the separating axis theorem. It can be used to detect whether two convex polygons overlap.

This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

12 Responses to Detecting Whether Two Boxes Overlap

  1. CharlesDemar says:

    I see your website needs some unique content.
    Writing manually is time consuming, but there is tool for this task.
    Just search for; Digitalpoilo’s tools

  2. Andrey says:

    Write a function which returns true if the two rectangles passed to it as arguments would overlap if drawn on a Cartesian plane. The rectangles are guaranteed to be aligned with the axes, not arbitrarily rotated.

  3. The non-overlapping experiment cases, including those which would overlap simply in straight or upright dimensions but are understandable in the other measurement.

  4. adult cycle says:

    I just received my brand new push bike today from Amazon and I have to say i`m really impressed.

  5. Most experienced web/GUI software engineers have worked with 2D boxes and have experienced the issue, and should know the best possible arrangement. In any case, they frequently don’t quickly see the rule that stretches out the thought past AABB’s to self-assertively arranged boxes.

  6. I am curious to find out what blog system you are utilizing?
    I’m having some minor security issues with my latest site and I would like to find something more
    risk-free. Do you have any recommendations?
    ebony tube video

  7. Not really. If it is just a microphone and a recorder, the radiated signal would be very small. A detector would be looking for anything coming from the recorder itself. I suppose a body search would be the usual approach.

  8. If some one wishes to be updated with newest technologies
    after that he must be pay a quick visit this site and be
    up to date everyday. zeloporn.com

  9. Amy says:

    This is a very great hints particularly to those new to blogosphere,
    short and precise info… Thanks for sharing this one.
    A must read article.

  10. apply for loan online payday advance loans for people with poor credit

  11. Appreciating the time and energy you put into your blog and in depth information you present.
    It’s good to come across a blog every once in a while that isn’t the same outdated rehashed material.

    Fantastic read! I’ve bookmarked your site and I’m including your RSS feeds to my Google account.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">