Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

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

Posted by tekpool on October 11, 2006

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

21 Responses to “Rectangle Intersection – Determine if two given rectangles intersect each other or not”

  1. Kyle said

    Thanks! I assigned each condition a variable name (above, below, left, and right). The resulting final condition in pretty (in ruby at least):

    not above and not below and not left and not right

    It’s intuitive: If touching, it will not be above, below, to the right, or to the left!

  2. […] own and immediatly had a very nasty chunk of code.  I knew I was doing something wrong.  I found this short article which immediatly made me think back to college CompSci with its simple solution.  I need to test […]

  3. ADHAR said

    i did not understand the second and the fourth conditions in the conditional expression i.e r2->right left and r2->bottom top.can you please help me with this.

  4. leek said

    The WordPress comment parser stripped out the < r1->, figuring it to be an HTML tag.

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

  5. Al said

    Not sure if this is the most effective but it has suited my purpose: find the bounding box and see if the sides are bigger than the 2 rectangles touching at 2 corners if you get my drift:

    private boolean overlap(int sx1, int sy1, int w1, int h1,
    int sx2, int sy2, int w2, int h2)
    {
    int leastx, leasty, mostx, mosty ;
    if ( sx1 < sx2 ) { leastx = sx1; mostx = sx2; }
    else { leastx = sx2; mostx = sx1; }
    if ( sy1 ( w1 + w2 ) ) return false ;
    if ( ( mosty – leasty ) > ( h1 + h2 ) ) return false ;
    return true;

    }

  6. Al said

    Whoa… lets try that again… formatting issues…


    private boolean overlap(int sx1, int sy1, int w1, int h1,
    int sx2, int sy2, int w2, int h2)
    {
    int leastx, leasty, mostx, mosty ;
    if ( sx1 < sx2 ) { leastx = sx1; mostx = sx2; }
    else { leastx = sx2; mostx = sx1; }
    if ( sy1 ( w1 + w2 ) ) return false ;
    if ( ( mosty - leasty ) > ( h1 + h2 ) ) return false ;
    return true;

    }

  7. Al said

    Ok, something is stripping out half my code…

        private boolean overlap(int sx1, int sy1, int w1, int h1,
                                int sx2, int sy2, int w2, int h2)
        {
            int leastx, leasty, mostx, mosty ;
            if ( sx1 < sx2 ) { leastx = sx1; mostx = sx2; }
            else  { leastx = sx2; mostx = sx1; }
            if ( sy1  ( w1 + w2 ) ) return false ;
            if ( ( mosty - leasty ) > ( h1 + h2 ) ) return false ;
            return true;
    
        }
    
  8. Al said

    Ok one more time. The scripts keep thinking that LT and GT symbols are tags even in preformatted text. Talk about overkill!

    private boolean overlap(int sx1, int sy1, int w1, int h1,
                                int sx2, int sy2, int w2, int h2)
        {
            int leastx, leasty, mostx, mosty;
            if (sx1 LESSTHAN sx2)
            {
                leastx = sx1;
                mostx = sx2;
            }
            else
            {
                leastx = sx2;
                mostx = sx1;
            }
            if (sy1 LESSTHAN sy2)
            {
                leasty = sy1;
                mosty = sy2;
            }
            else
            {
                leasty = sy2;
                mosty = sy1;
            }
            if ((mostx - leastx) GREATERTHAN (w1 + w2)) return false;
            if ((mosty - leasty) GREATERTHAN (h1 + h2)) return false;
            return true;
    
        }
    

    Sigh.

  9. Jo said

    Hi Al,
    good idead, but propably you missed some values (h1,h2,w1,w2) to integrate into your calculations when trying to find mostx, mosty:

    private boolean overlap(int sx1, int sy1, int w1, int h1,
    int sx2, int sy2, int w2, int h2)
    {
    int leastx, leasty, mostx, mosty;
    if (sx1 LESSTHAN sx2)
    {
    leastx = sx1;
    mostx = sx2 + w2;
    }
    else
    {
    leastx = sx2;
    mostx = sx1 + w1;
    }
    if (sy1 LESSTHAN sy2)
    {
    leasty = sy1;
    mosty = sy2 + h2;
    }
    else
    {
    leasty = sy2;
    mosty = sy1 + h1;
    }
    if ((mostx – leastx) GREATERTHAN (w1 + w2)) return false;
    if ((mosty – leasty) GREATERTHAN (h1 + h2)) return false;
    return true;

    }

  10. итак: неподражаемо…

  11. persick said

    AS3 code:
    public class Rect
    {
    public var x1: Number, y1: Number;
    public var x2: Number, y2: Number;
    …..
    }
    function intersect(r1:Rect, r2:Rect)
    {
    var on_x: Boolean = (r2.x1 >= r1.x1 && r2.x1 = r2.x1 && r1.x1 = r1.y1 && r2.y1 = r2.y1 && r1.y1 <= r2.y2);

    return on_x && on_y;
    }

  12. persick said

    buggy comment display 😦

  13. Hein Thet said

    This was one of the interview exam i took yesterday..! got it sorted out, but in slightly different way.

  14. Az said

    Why negate?

    The intersect condition is much simpler than how you have expressed in those 9 segments. There are really only 2 “segments” and you only need to check for one corner in each.

    It is simple:

    IF
    TOPLEFT is in S1 || S2 || S4 || S5
    AND
    BOTTOMRIGHT is in S5 || S6 || S8 || S9
    then you have intersecting rectangles.

    The code has the same number of conditions as what the blog example has:

    r2->Right > r1->Left &&
    r2->Bottom Top &&
    r2->Top > r1->Right &&
    r2->Left Bottom

    • BMX said

      That doesn’t handle the crossing case for two rectangles. Corners need not be contained within the bounds of the other rectangle for an intersection to occur.

  15. Az said

    r2->Right > r1->Left &&
    r2->Bottom Top &&
    r2->Top > r1->Right &&
    r2->Left Bottom
    
  16. Az said

    r2->Right > r1->Left &&
    r2->Bottom Top &&
    r2->Top > r1->Bottom &&
    r2->Left Right
    
  17. Az said

    r2->Right > r1->Left &&
    r2->Bottom < r1->Top &&
    r2->Top > r1->Bottom &&
    r2->Left < r1->Right

  18. […] Now, step two: Check to see if our bullet resides within the bounds of each enemy. Here we need a little math: […]

  19. […] The original function – and an alternative description of why it works – can be found here: https://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-int&#8230; […]

  20. Hello friends, its fantastic paragraph concerning educationand fully explained, keep it up all the time.|

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: