CareerCup

The conditions to verify if the rectangles do NOT intersect are easier.

There are 4 generic intersection cases, given any 2 rectangles, get 4 end points for one of the rectangles and check if any of them (point) lies inside the rectangle 1.

1. For each line segment of rectangle-1, check whether any of the line segments of the other rectangle-2 intersect.
2. Two line segments intersect if the end points of one line lie on either side of the other line. (Ref: Introduction to Algorithms by Cormen, Rivest for the algorithm. Chapter-Computational Geometry)

lets assume (x1,y1) be bottom left and (x2,y2) as top right .. all we need to check for non intersection is that either of the co-ordinates(x,y) of other rectangle should follow :
x should not be in region [x1,x2] and y should not be in [y1,y2] for each pair of co-ordinates...

If you have given topLeft and bottomLeft of rectangle then, all you need to find the center of each rectangle and find the distance between two centers and compare it with sum of heights and widths of two rectangle.
E.g.
If R1 topLeft(x1,y1) and bottomRight(x2,y2)
R1 topLeft(x3,y3) and bottomRight(x4,y4)
Center of R1 will be R1C((x2-x1)/2, (y2-y1)/2), Lets say (c1X, c1Y)
Center of R2 will be R2C((x4-x3)/2, (y4-y3)/2) lets say (c2X, c2Y)

Width of R1 is W1(c1x-x1) and height is H1(c1y - y1 )
Width of R2 is W2(c2x-x3) and height is H2(c2y - y3 )

Now if ((c2x - c1X)< (W1 + W2) && (c2y-c1y) < (H1+H2)) if this condition is satisfied then two rectangles are intersected.

This problem actually has a really easy solution. Let's assume that top-x, y are always smaller than buttom-x, y for one rectangle. In other words, assuming the origin is on the top left, and y axis goes downward.

Let's assume (tx1, ty1) is the point of top left of rectangle 1, (bx1, by1) is the point on the bottom right. the same notation applies to rectangle 2 as (tx2, ty2) and (bx2, by2)

In this case, we let A= [max(tx1, tx2), max(ty1, ty2) ] and B = [min(bx1, bx2), min(by1, by2)]. If B is strictly on the bottom-right of A, they intersect, otherwise they aren't. The correctness can be easily proven.

A unique rectangle cannot be determined from the end points of a single diagonal of a rectangle (think about it...)

So, the rectangles intersect only if the two diagonals intersect, otherwise it is always possible to draw rectangles with infinitesimally small breadth so that they don't intersect.

/**
* Determines whether or not this <code>Rectangle</code> and the specified
* <code>Rectangle</code> intersect. Two rectangles intersect if
* their intersection is nonempty.
*
* @param r the specified <code>Rectangle</code>
* @return <code>true</code> if the specified <code>Rectangle</code>
* and this <code>Rectangle</code> intersect;
* <code>false</code> otherwise.
*/
public boolean intersects(Rectangle r) {
int tw = this.width;
int th = this.height;
int rw = r.width;
int rh = r.height;
if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
return false;
}
int tx = this.x;
int ty = this.y;
int rx = r.x;
int ry = r.y;
rw += rx;
rh += ry;
tw += tx;
th += ty;
// overflow || intersect
return ((rw < rx || rw > tx) &&
(rh < ry || rh > ty) &&
(tw < tx || tw > rx) &&
(th < ty || th > ry));
}

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

#include<stdio.h>
typedef struct rect
{
	unsigned lower_left_X;
 	unsigned lower_left_Y;  
	unsigned upper_right_X;
	unsigned upper_right_Y;
} rectangle;
int main()
{
	rectangle r1 = {1,1,4,3};
	rectangle r2 = {4,4,5,5};
	if ((r1.lower_left_X    > r2.upper_right_X) ||  
		(r1.lower_left_Y    > r2.upper_right_Y) ||
		(r1.upper_right_X   < r2.lower_left_X)  ||
		(r1.upper_right_Y   < r2.lower_left_Y))
	{
		printf("Rectangle does not intersect\n");
	}
	else
	{
		printf("Rectangle Intersects\n");
	}
	return 0;
}