Overlapping rectangles

Overlapping rectangles

Post by Alan McFarlan » Sat, 08 Jan 2000 04:00:00



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

Post by Hans-Bernhard Broeke » Sat, 08 Jan 2000 04:00:00



> 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

Post by Richard Kinc » Sat, 08 Jan 2000 04:00:00



> > 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.
 
 
 

1. Overlapping rectangles -- HELP

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

2. RGB565 vs RGB555

3. Merging unit sqaures into non-overlapping rectangles

4. Help: Howto paste several graphics onto a page

5. Polygon from overlapping Rectangles?

6. Character animation

7. Overlapping rectangles

8. Computing a set overlapping rectangles

9. Overlapping rectangles: how to determine?

10. Q: Outline of overlapping rectangles

11. What is a simple algorithm for creating non-overlapping rectangles?

12. Checking rectangle overlap in a plane