From: "R.G. Morgan" <r DOT g DOT morgan AT ncl DOT ac DOT uk>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: collision detection
Date: Thu, 02 Oct 1997 09:53:22 +0100
Organization: University of Newcastle upon Tyne
Message-ID: <34336102.3E755A19@ncl.ac.uk>
References: <C1256524 DOT 002EA05E DOT 00 AT vega DOT ads DOT it>
NNTP-Posting-Host: hopside.ncl.ac.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 45
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

I have been doing some things like this myself, and I find it easiest to
think of the two rectangles as being two pairs of intervals.  One
interval is on the x line (x1,x2) for both rectangles, and (y1,y2) is on
the y-line.  Only if both pairs of intervals overlap (the two x
intervals, and the two y intervals) will there be an overlap.
	Testing for the corners being included in the other rectangle isn't
useful: think of the red cross sign as being made up of two overlapping
rectangles.
	With the rule x1 <= x2 and y1 <= y2 (and inclusive coords) we have;

bool
overlap(RECT a, RECT b)
{
	return  (a.x1 <= b.x2 && a.x2 >= b.x1) &&
		(a.y1 <= b.y2 && a.y2 >= b.y1);
}

  If this is correct (from memory, as I don't have the code in front of
me), I think is it close to being optimal as the eight scalar quantities
involved are used only once, and there are only 4 tests.

G DOT DegliEsposti AT ads DOT it wrote:
> Andrew Deren wrote:
> > Does anyone know how to detect if two rectangles overlap each 
> > other at some point. Let's say we have something like this:
> >
> > typedef struct RECT {
> >    int x1, y1, x2, y2;
> > } RECT;

> I alway use another way, which costs almost the same but is simplier 
> to write:
>  if A and B overlap each other then they have an intersection, so I 
> test if they intersect and the intersection is a real rectangle:
> 
> This tests if the intersection of A and B is a valid rectangle (ie 
> x1<x2 and y1<y2)
> 
> // A and B must be valid rectangles...
> bool overlap(RECT A, RECT B)
> {
>      // I = intersect(A,B); return isvalid(I);
>      return (min(A.x2,B.x1) < max(A.x1,B.x2)) && (min(A.x2,B.x1) <
> max(A.x1,B.x2))
> }