Monday, February 28, 2011

Check if two rectangles intersect

This is a one of the classic problems in graphics programming and game development. So, let's see how we can solve it.

Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. As you move down the screen, the y value increases. And, as you move right the x value increases.

For the general purpose of this post, assume that we have a right-handed coordinate system where the origin is at the bottom-left screen such that it is exactly like the coordinate system we learn in high school algebra. Also, the rectangles that we have to check are on that coordinate system and are identified by the coordinates of their top-left corner and bottom right corner. For instance:

Here are scenarios where we consider two rectangles as intersecting each other:

Of course, those figures are just special cases of intersecting rectangles. There are many more ways to draw them, but four figures should give us enough information about what considered intersection. However, to solve this problem it is better to focus on when two rectangles do not intersect.

Here are example of non-intersecting rectangles:

From those pictures, we can infer that two rectangles are not intersecting each other if they have one of the four conditions:

  1. Right edge of blue is closer to the left of the screen than the left edge of red
  2. Bottom edge of blue is further from the bottom of the screen than the top edge of red
  3. Top edge of blue is closer to the bottom of the screen than the bottom edge of red
  4. Left edge of blue is further from the left of the screen than the right edge of red

So, if our rectangles don't have any of those conditions, then they intersect one another! Here is the code:

#include<iostream>
using namespace std;

struct Point
{
  float x;
  float y;
};

struct Rect
{
  Point topLeft;
  Point bottomRight;
};

bool isIntersect(Rect rect1, Rect rect2)
{
  if (rect1.topLeft.x >= rect2.bottomRight.x 
      || rect1.bottomRight.x <= rect2.topLeft.x 
      || rect1.topLeft.y <= rect2.bottomRight.y 
      || rect1.bottomRight.y >= rect2.topLeft.y)
    return false;
    
  return true;
}

Our rectangles are defined by their top-left and bottom-right vertices each of which is defined by a pair of x and y coordinates. Thus, there are two structs. One for the point and one for the rectangle.

Our method to determine intersection is simple, we just have to check for all four conditions explained above. If any of those conditions is true then our rectangles do not intersect. Notice that we use x values when comparing the distance of right and left edges of the rectangles. Also, we only use y values when comparing the distances of top and bottom edges of the rectangles.

That's it for this post. Please leave a comment if you have any question / suggestion. Thanks

8 comments:

  1. Hello, I was reading your post wich by the way is great, however in the isIntersect function I found an error. I fixed it, check it out.


    bool isIntersect(Rect rect1, Rect rect2)
    {
    if (rect1.topLeft.x >= rect2.bottomRight.x
    || rect1.bottomRight.x <= rect2.topLeft.x
    || rect1.topLeft.y >= rect2.bottomRight.y
    || rect1.bottomRight.y <= rect2.topLeft.y)
    return false;

    return true;
    }

    ReplyDelete
  2. Hi Jose,

    Thanks for commenting. I went and re-ran the code through additional tests but couldn't find the error. Please let me know which data set you used to test the code.

    The fixed code you gave will fail in some cases such as intersection between rectangle defined by (3, 2) and (5,1), and rectangle defined (1,3) and (4,1).

    Thanks,

    ReplyDelete
  3. I think it depends which way your axis is orientated, i.e is the Y-axis going up from the X or down.

    y x _ _ _ _
    | |
    | |
    |_ _ _ _ x VS |

    The initial solution is suited for the left, and the comments solution for the right. Please correct me if I am talking rubbish.

    ReplyDelete
  4. |
    |
    |
    |_ _ _ _

    vs

    _ _ _ _
    |
    |
    |

    my previous post got messed up a little with the diagrams!

    ReplyDelete
    Replies
    1. Yup you're right! This depends on the orientation of the coordinate system. So, knowing the orientation is a must before solving this problem.

      Delete
  5. this returns true if the two rectangles DO intersect correct?

    ReplyDelete
  6. public boolean checkOverlap(Rectangle r2){
    if (this.upperX >= r2.lowerX
    || this.lowerX <= r2.upperX
    || this.upperY <= r2.lowerY
    || this.lowerY >= upperY){

    return false;
    }

    return true;
    }

    ReplyDelete
  7. Simple and good solution....
    Thanks a million ....

    ReplyDelete