11
How to check if two rectangles intersect or not ?
Algorithm Analysis and Design
Computational Geometry

First of all, let's define the rectangles and points in the following structures:

struct Point
{
       int x;
       int y;
};

struct Rectangle
{
       Point topLeft;                       // Denotes the top-left point of the rectangle
       Point bottomRight;                   // Denotes the bottom-right point of the rectangle
};

Given two rectangles R1 and R2 . It is easy to visualize that the given two rectangles can not be intersect if one of the following conditions is true.

Condition 1: When left edge of R1 is on the right of R2's right edge. ( That is , R1 is completely on the right of R2).

Condition 2: When right edge of R1 is on the left of R2's left edge. ( That is , R1 is completely on the left of R2).

Condition 3: When top edge of R1 is on bottom of R2's bottom edge ( That is , R1 is completely under R2).

Condition 4: When bottom edge of R1 is on top of R2's top edge ( That is , R1 is completely over R2).

Conditions

Here is the following code based on the above conditions:

 void RectIntersect( Rectangle R1 , Rectangle Rt2 )
    {
      if   (  (  R1.topLeft.x  >  R2.bottomRight.x  )||  (  R1.bottomRight.x  <  R2.topLeft.x  )  || (  R1.topLeft.y > R2.bottomRight.y ) ||
           (   R1.bottomRight.y  <  R2.topLeft.y   ) )
 {
cout<<" Non - Intersecting";
   }
      else
       {
  cout<<" Intersecting";
       }      
    }

We can also apply De Morgan's law :

! ( Condition1 || Condition2 || Condition3 || Condition4 ) = ( ! Condition1 ) && ( ! Condition2 ) && ( ! Condition3 ) && ( ! Condition4 )

Here is the following code based on the above conditions:

   void RectIntersect( Rectangle R1 , Rectangle R2 )
    {
    if (  (  R1.topLeft.x  <  R2.bottomRight.x  )  &&  (   R1.bottomRight.x   >  R2.topLeft.x  )  &&
       (  R1.topLeft.y  <  R2.bottomRight.y  )  &&
         (  R1.bottomRight.y  >  R2.topLeft.y  )  )
      {
  cout<<"Intersecting"
      }
      else
      {
  cout<<"  Non - Intersecting";   
}
    }
Author

Notifications

?