Skip to main content
GameDev.net gamedev.net
🔒 Locked

Rectangle Intersection

Started by RDragon1 Feb 3, 2005 at 7:20 PM 2 replies 20.6k views
Original Post
RDragon1
RDragon1
Hey guys, Disapointed that the search feature is broken, but I have a simple problem. I need an efficient way to determine if two rectangles intersect. Here is the current version that I am working at:

bool Rect::DoesIntersect( const Rect& other ) const
{
	//see which rectangle is 'bigger' - this is done as the bigger
	//rect can never lie completely inside the smaller

	unsigned int this_area = Width() * Height();
	unsigned int other_area = other.Width() * other.Height();

	const Rect* a;
	const Rect* b;

	if( this_area > other_area )
	{
		a = this;
		b = &other
	}
	else
	{
		a = &other
		b = this;
	}

	//rect 'a' can never lie completely 'inside' rect 'b'

	//check top-left point
	if( b->top >= a->top && b->top <= a->bottom )
		if( b->left >= a->left && b->left <= a->right )
			return true;

	//check top-right point
	if( b->top >= a->top && b->top <= a->bottom )
		if( b->right >= a->left && b->right <= a->right )
			return true;

	//check bottom-left point
	if( b->bottom >= a->top && b->bottom <= a->bottom )
		if( b->left >= a->left && b->left <= a->right )
			return true;

	//check bottom-right point
	if( b->bottom >= a->top && b->bottom <= a->bottom )
		if( b->right >= a->left && b->right <= a->right )
			return true;

	return false;
}
Any tips or suggestions on cutting down all of those comparisons would be greatly appreciated!
directrix
directrix
// check if 2 rectangles intersectinline bool RectRectIntersection(const fRECT& rect1, const fRECT& rect2){	if(rect1.bottom < rect2.top)		return false;	if(rect1.top > rect2.bottom)		return false;	if(rect1.right < rect2.left)		return false;	if(rect1.left > rect2.right)		return false;	return true;}
Melekor
Melekor
If I understand it correctly, your code is testing to see if rectangle 1 is inside rectangle 2. That's not what intersection is. Intersection means "do they overlap at all?"

In c++:

If all you care about is a boolean, you could use this

bool Rect::intersect(const Rect& other) const{	return !(left > other.right || right < other.left ||		top > other.bottom || bottom < other.top);}


Otherwise, if you want to make a function that returns a rectangle containing the overlapping area:

Rect Rect::operator &(const Rect& other) const{	if(intersect(other))	{		return Rect(max(left, other.left), max(top, other.top),		min(right, other.right), min(bottom, other.bottom));	}	return Rect(0,0,0,0);}
RDragon1
RDragon1
Thanks for the tip - my code does test to see if any part of the smaller rectangle lies within the larger, by seeing if any corner lies within the bounds of the rectangle. It looks like the negative logic is easier to prove - under what conditions would they not be intersecting. Thanks!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.