Tuesday, February 28, 2012

Two Rectangles overlap or not

Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.


Two overlapping rectangles. A rectangle can be defined by its upper left and lower right corner.

 Assume that the two rectangles are given as point (P1, P2) and (P3, P4) respectively. One direct way to attempt. How about asking yourself how the two rectangles cannot overlap each other? Two rectangles do not overlap when one is above/below, or to the left/right of the other rectangle.


The condition’s expression is:
! ( P2.y < P3.y || P1.y > P4.y || P2.x < P3.x || P1.x > P4.x )

Using De Morgan’s law, we can further simplify the above expression to:
( P2.y = P3.y && P1.y = P4.y && P2.x = P3.x && P1.x = P4.x )
 
Code:
/*
(P1,P2)=rect1,(P3,P4)=rect2 
 P1,P3-->topleft points
P2,p4-->bottomright points 
*/ 
#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;
} 

2 comments:

  1. http://www.leetcode.com/2011/05/determine-if-two-rectangles-overlap.html

    ReplyDelete
  2. http://mycareerstack.com/questions/?company=Microsoft

    ReplyDelete