Overlapping rectangles

Overlapping rectangles

Q1. Given two rectangles - (ax1,ay1,ax2,ay2) & (bx1,by1,bx2,by2), what is
the best (fastest rather than smallest) algorithm in C or C++ to determine
if the rectangles overlap.

Q2. Given that the two rectangles overlap, is it possible to adjust the
algorithm to return an integer determining where they overlap?
--
Alan McFarlane

Overlapping rectangles

> Q1. Given two rectangles - (ax1,ay1,ax2,ay2) & (bx1,by1,bx2,by2), what is
> the best (fastest rather than smallest) algorithm in C or C++ to determine
> if the rectangles overlap.

That's simple. Check for overlap of the ranges covered by both of them,
on each axis. Assuming x2>x1m and y2>y1 for both a and b, the test is:

if ((bx2<ax1) || (bx1>ax2))
return("no overlap");
if ((by2<ay1) || (by1>ay2))
return("no overlap");
return("overlap");

Quote:> Q2. Given that the two rectangles overlap, is it possible to adjust the
> algorithm to return an integer determining where they overlap?

No. That's because a single integer cannot possibly answer this
"where?" question. The answer would another rectangle, i.e. 4 numbers
to describe them.

--

Even if all the snow were burnt, ashes would remain.

Overlapping rectangles

> > Q2. Given that the two rectangles overlap, is it possible to adjust the
> > algorithm to return an integer determining where they overlap?
> No. That's because a single integer cannot possibly answer this
> "where?" question. The answer would another rectangle, i.e. 4 numbers
> to describe them.

Easiest calculation is via contra-positive half-planes.

I thought this would be trivial problem, but...

If I have the 4 vertices of two rectangles, is there a quick and easy way
to tell if they overlap.  I don't even need the overlapping region!

All I've thoght of so far is brute force checing several cases.
eg.  one in other, other in one, one with vertices in other, other with
verticies in one, one with line through other, other with line through
one...  I must be missing the boat big time here!

Any help would be GREATLY appreciated!

Thanks,
-Gary