From: mert0407 AT sable DOT ox DOT ac DOT uk (George Foot)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: collision detection
Date: 17 Oct 1997 18:24:43 GMT
Organization: Oxford University, England
Lines: 39
Distribution: World
Message-ID: <628ahb$qb1$1@news.ox.ac.uk>
References: <C1256524 DOT 002EA05E DOT 00 AT vega DOT ads DOT it> <627er1$jsm AT whitbeck DOT ncl DOT ac DOT uk>
NNTP-Posting-Host: sable.ox.ac.uk
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

On 17 Oct 1997 10:32:01 GMT in comp.os.msdos.djgpp R.G. Morgan
(r DOT g DOT morgan AT ncl DOT ac DOT uk) wrote: 

: > Rob Farley wrote:
: >> >> Does anyone know how to detect if two rectangles overlap each other at
: >> >> some point. Let's say we have something like this:

: > Given two rectangles, A and B, check to see if any of the vertices of B
: > lie on A.  If this is true, then there must be overlap.

: Not the case; consider the Red Cross Sign decomposed into 2 rectangles.
: Although if you check often enough, this shouldn't happen.

IMHO the `best' way, in one dimension (for a line segment), is:

if ((a.min > b.max) || (b.min > a.max)) {
 /* no overlap */
} else {
 /* overlap */
}

Simply put, if one item's smallest-valued point is greater than the other's
largest-valued, there is no overlap.

In two dimensions for a rectangular region this becomes:

if (((a.x.min > b.x.max) || (b.x.min > a.x.max))
 || ((a.y.min > b.y.max) || (b.y.min > a.y.max))) {
 /* no overlap */
} else {
 /* overlap */
}

A strong point of this is that the OR operators quickly shortcircuit if there
is no overlap. 

-- 
George Foot <mert0407 AT sable DOT ox DOT ac DOT uk>
Merton College, Oxford