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

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

- Raw text -