Rectangle Intersection – Determine if two given rectangles intersect each other or not

Q: Rectangle Intersection: Determine if two given rectangles intersect each other or not

Definitions:

Intersect: Two Rectangles intersect each other if the share a common area.

Assumptions:

• Both the rectangles are aligned with the x and y axes.
• Rectangles just touching each other are considered as non-intersecting.

First let’s create a data structure for use in our problem. Rectangle Intersection algorithms are usually used in graphics problems. Depending on the precision needed to represent the co-ordinates, you may choose the required data type. In this case, I am going to use a LONG.

I am also basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.

struct 
{ 
    LONG    left; 
    LONG    top; 
    LONG    right; 
    LONG    bottom; 
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2) 
{ 
    return ! ( r2->left > r1->right 
        || r2->right left 
        || r2->top > r1->bottom 
        || r2->bottom top 
        ); 
}

The above algorithm finds the conditions at which the rectangles do not intersect and then negates the values to get the result. There is a straight forward way of doing the same algorithm, but it requires far more conditions than the one above. Consider the diagram below

  S1   |         S2          |   S3 
       |                     | 
    TOP|LEFT                 | 
----------------------------------- 
       |                     | 
       |                     | 
       |                     | 
  S4   |         S5          |   S6 
       |                     | 
       |                     | 
----------------------------------- 
       |                RIGHT|BOTTOM 
       |                     | 
  S7   |         S8          |   S9

This is an illustration of one of the rectangles (R1). The top left corner of R2 can like in any of the 9 segments, S1 through S9. Based on each of these cases, and depending on the position of the other vertices, it can be determined whether the two rectangles R1 and R2 intersect each other. E.g. If R2’s top left corner is in S1, the bottom right corner needs to be in S5 or beyond (S5,S6,S8,S9) for the rectangles to intersect. Or if the top left corner of R2 is in S5, it is an automatic case of intersection. Clearly, in this case there are a lot of cases to consider and therefore and lot of conditions to check.

The conditions where the rectangles do not intersect, is where the bounds of one Rectangle is beyond the bounds of the other. The conditions are pretty straightforward as shown in the code above. Negating this value solves the original problem.

There is one more conditions (negation) that can be avoided by changing the inner condition. I will leave that as an exercise for the reader.

NOTE: For all invalid rectangles passed to the function, the return value is always false. You can also choose to return error codes after checking for validity.

Advertisements