Problem
Write a function to check if two rectangles defined as below, have common area or not.
The functions take the top left and bottom right coordinate as input
and return 1 if they have common area, otherwise return 0.
Solution
Assume all rectangle edges are parallel to axis.
This assumption just makes examiner happy because two points cannot determine a rectangle if we consider rotation.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Detect whether two rectangles have common area or not
Created Date : 19-06-2013
Last Modified : 21-06-2013
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
typedef struct{
int x;
int y;
} Point;
bool IsPointInside(Point &p, Point& topLeft, Point& bottomRight)
{
if(p.x <= bottomRight.x && p.x >= topLeft.x && p.y <= bottomRight.y && p.y >= topLeft.y){
return true;
}
return false;
}
bool HasCommonArea(Point& topLeft1, Point& bottomRight1, Point& topLeft2, Point& bottomRight2)
{
Point rectVertice1[4] = {
{topLeft1.x, topLeft1.y},
{bottomRight1.x, topLeft1.y},
{topLeft1.x, bottomRight1.y},
{bottomRight1.x, bottomRight1.y}
};
for(int i = 0; i < 4; ++i){
if(IsPointInside(rectVertice1[i], topLeft2, bottomRight2)){
return true;
}
}
Point rectVertice2[4] = {
{topLeft2.x, topLeft2.y},
{bottomRight2.x, topLeft2.y},
{topLeft2.x, bottomRight2.y},
{bottomRight2.x, bottomRight2.y}
};
for(int i = 0; i < 4; ++i){
if(IsPointInside(rectVertice2[i], topLeft1, bottomRight1)){
return true;
}
}
return false;
}
void DoTest(Point& topLeft1, Point& bottomRight1, Point& topLeft2, Point& bottomRight2)
{
cout << "Rectangle 1 is ";
cout << "Topleft(" << setw(2) <<topLeft1.x << ", ";
cout << setw(2) <<topLeft1.y << ")";
cout << "bottomRight(" << setw(2) <<bottomRight1.x << ", ";
cout << setw(2) <<bottomRight1.y << ")" << endl;
cout << "Rectangle 2 is ";
cout << "Topleft(" << setw(2) << topLeft2.x << ", ";
cout << setw(2) <<topLeft2.y << ")";
cout << "bottomRight(" << setw(2) <<bottomRight2.x << ", ";
cout << setw(2) <<bottomRight2.y << ")" << endl;
if(HasCommonArea(topLeft1, bottomRight1, topLeft2, bottomRight2)){
cout << "The two rectangles have common area" << endl;
}
else{
cout << "The two rectangles DON'T have common area" << endl;
}
cout << "-------------------------------" << endl << endl;
}
int main(int argc, char* argv[])
{
// Case 1: rectangle 1 contains rectangle 2
cout << "--- Case 1: rectangle 1 contains rectangle 2 " << endl;
Point topLeft1 = {1, 1};
Point bottomRight1 = {20, 20};
Point topLeft2 = {2, 2};
Point bottomRight2 = {15, 15};
DoTest(topLeft1, bottomRight1, topLeft2, bottomRight2);
// Case 2: rectangle 2 contains rectangle 1
cout << "--- Case 2: rectangle 2 contains rectangle 1 " << endl;
topLeft1.x = 10;
topLeft1.y = 10;
bottomRight1.x = 20;
bottomRight1.y = 20;
topLeft2.x = 2;
topLeft2.y = 2;
bottomRight2.x = 115;
bottomRight2.y = 115;
DoTest(topLeft1, bottomRight1, topLeft2, bottomRight2);
// Case 3: rectangle1 intersects rectangle 2
cout << "--- Case 3: rectangle1 intersects rectangle 2 " << endl;
topLeft1.x = 10;
topLeft1.y = 10;
bottomRight1.x = 20;
bottomRight1.y = 20;
topLeft2.x = 12;
topLeft2.y = 12;
bottomRight2.x = 115;
bottomRight2.y = 115;
DoTest(topLeft1, bottomRight1, topLeft2, bottomRight2);
// Case 4: rectangle1 does not have common area with rectangle 2
cout << "--- Case 3: rectangle1 intersects rectangle 2 " << endl;
topLeft1.x = 10;
topLeft1.y = 10;
bottomRight1.x = 20;
bottomRight1.y = 20;
topLeft2.x = 22;
topLeft2.y = 22;
bottomRight2.x = 115;
bottomRight2.y = 115;
DoTest(topLeft1, bottomRight1, topLeft2, bottomRight2);
// Case 5: random input
cout << "--- Case 5: random input " << endl;
for(int i = 0; i < 20; ++ i){
topLeft1.x = rand() % 20 + 1;
topLeft1.y = rand() % 20 + 1;
bottomRight1.x = rand() % 20 + 1 + topLeft1.x;
bottomRight1.y = rand() % 20 + 1 + topLeft1.y;
topLeft2.x = rand() % 20 + 1;
topLeft2.y = rand() % 20 + 1;
bottomRight2.x = rand() % 20 + 1 + topLeft2.x;
bottomRight2.y = rand() % 20 + 1 + topLeft2.y;
DoTest(topLeft1, bottomRight1, topLeft2, bottomRight2);
}
return 0;
}
Output
--- Case 1: rectangle 1 contains rectangle 2
Rectangle 1 is Topleft( 1, 1)bottomRight(20, 20)
Rectangle 2 is Topleft( 2, 2)bottomRight(15, 15)
The two rectangles have common area
-------------------------------
--- Case 2: rectangle 2 contains rectangle 1
Rectangle 1 is Topleft(10, 10)bottomRight(20, 20)
Rectangle 2 is Topleft( 2, 2)bottomRight(115, 115)
The two rectangles have common area
-------------------------------
--- Case 3: rectangle1 intersects rectangle 2
Rectangle 1 is Topleft(10, 10)bottomRight(20, 20)
Rectangle 2 is Topleft(12, 12)bottomRight(115, 115)
The two rectangles have common area
-------------------------------
--- Case 3: rectangle1 intersects rectangle 2
Rectangle 1 is Topleft(10, 10)bottomRight(20, 20)
Rectangle 2 is Topleft(22, 22)bottomRight(115, 115)
The two rectangles DON'T have common area
-------------------------------
--- Case 5: random input
Rectangle 1 is Topleft( 2, 8)bottomRight(17, 9)
Rectangle 2 is Topleft(10, 5)bottomRight(29, 24)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft( 3, 5)bottomRight( 9, 11)
Rectangle 2 is Topleft( 2, 8)bottomRight( 4, 20)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft(16, 3)bottomRight(24, 20)
Rectangle 2 is Topleft(12, 5)bottomRight(15, 19)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft(13, 3)bottomRight(15, 20)
Rectangle 2 is Topleft(19, 16)bottomRight(27, 23)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft(12, 19)bottomRight(22, 32)
Rectangle 2 is Topleft( 8, 20)bottomRight(24, 35)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft( 4, 12)bottomRight( 7, 26)
Rectangle 2 is Topleft(14, 5)bottomRight(16, 17)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft(14, 9)bottomRight(22, 14)
Rectangle 2 is Topleft( 3, 18)bottomRight(21, 38)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 4, 2)bottomRight(14, 21)
Rectangle 2 is Topleft(17, 16)bottomRight(28, 19)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 9, 7)bottomRight(10, 10)
Rectangle 2 is Topleft( 5, 9)bottomRight(12, 15)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft(11, 10)bottomRight(22, 21)
Rectangle 2 is Topleft( 7, 2)bottomRight(21, 11)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft(10, 4)bottomRight(15, 19)
Rectangle 2 is Topleft(17, 1)bottomRight(24, 18)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft(12, 9)bottomRight(17, 29)
Rectangle 2 is Topleft( 7, 4)bottomRight(25, 23)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft(19, 3)bottomRight(29, 5)
Rectangle 2 is Topleft(14, 16)bottomRight(34, 35)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 5, 11)bottomRight(23, 18)
Rectangle 2 is Topleft(14, 7)bottomRight(16, 13)
The two rectangles have common area
-------------------------------
Rectangle 1 is Topleft( 5, 13)bottomRight(16, 23)
Rectangle 2 is Topleft(18, 14)bottomRight(36, 27)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 7, 11)bottomRight( 9, 28)
Rectangle 2 is Topleft(16, 8)bottomRight(32, 23)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft(12, 13)bottomRight(23, 24)
Rectangle 2 is Topleft( 2, 5)bottomRight( 9, 16)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 8, 12)bottomRight(16, 30)
Rectangle 2 is Topleft(18, 8)bottomRight(32, 12)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 6, 10)bottomRight(16, 29)
Rectangle 2 is Topleft( 2, 9)bottomRight( 5, 16)
The two rectangles DON'T have common area
-------------------------------
Rectangle 1 is Topleft( 7, 11)bottomRight(21, 20)
Rectangle 2 is Topleft( 1, 12)bottomRight( 4, 28)
The two rectangles DON'T have common area
-------------------------------
Press any key to continue . . .