Jump to content
  • Advertisement
Sign in to follow this  
mike74

rectangle-rectangle intersection

This topic is 4772 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Could someone tell me the fastest way to determine if two axis-parallel rectangles intersect? Here's what I have so far: bool pointinregion(Point p, Range r) { if ( p.x >= r.x0 && p.x <= r.x1 && p.y >= r.y0 && p.y <= r.y1) return true; else return false; } bool intersects(Range r0, Range r1) { if (pointinregion(Point(r0.x0, r0.y0), r1)) return true; else if (pointinregion(Point(r0.x1, r0.y0), r1)) return true; else if (pointinregion(Point(r0.x0, r0.y1), r1)) return true; else if (pointinregion(Point(r0.x1, r0.y1), r1)) return true; else if (pointinregion(Point(r1.x0, r1.y0), r0)) return true; else if (pointinregion(Point(r1.x1, r1.y0), r0)) return true; else if (pointinregion(Point(r1.x0, r1.y1), r0)) return true; else if (pointinregion(Point(r1.x1, r1.y1), r0)) return true; else return false; } mike http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
Advertisement
Take the four corner points of rectangle 1, and check if each point is inside or outside the rectangle 2. If (numInside > 0 && numOutside > 0) then they must intersect, because if (numInside == 4)(meaning numOutside==0) r1 is inside r2, if (numOutside == 4)(meaning numInside==0), r2 is inside r1, or they don't intersect at all.

But of course, this is if you want to check for intersection, not collision detection.

Share this post


Link to post
Share on other sites
something like


bool Intersection(RECT& rect1, RECT& rect2)
if(rect1.left > rect2.right)
{
return(false);
}
if(rect1.right < rect2.left)
{
return(false);
}
if(rect1.top > rect2.bottom)
{
return(false);
}
if(rect1.bottom < rect2.top)
{
return(false);
}
//there is an intersection.
return(true);
}




Where left,right,top and bottom are the sides of the rectangle.

What this does is test to see if they are not intersecting, I think its quicker then the way you are doing it at the moment but not sure if its the fastest way.

Share this post


Link to post
Share on other sites
I don't know where you got this, but it's not right. What if rect2 is inside rect1?

mike
http://www.coolgroups.com/

Quote:
Original post by grekster
something like

*** Source Snippet Removed ***

Where left,right,top and bottom are the sides of the rectangle.

What this does is test to see if they are not intersecting, I think its quicker then the way you are doing it at the moment but not sure if its the fastest way.


Share this post


Link to post
Share on other sites
If one rectangle is inside another, it needs to return true. This doesn't do that.

mike
http://www.coolgroups.com/

Quote:
Original post by clb
Take the four corner points of rectangle 1, and check if each point is inside or outside the rectangle 2. If (numInside > 0 && numOutside > 0) then they must intersect, because if (numInside == 4)(meaning numOutside==0) r1 is inside r2, if (numOutside == 4)(meaning numInside==0), r2 is inside r1, or they don't intersect at all.

But of course, this is if you want to check for intersection, not collision detection.


Share this post


Link to post
Share on other sites
Quote:
Original post by mike74
I don't know where you got this, but it's not right. What if rect2 is inside rect1?


if rect 2 is inside rect1 it will return true. is that not what you want?

Share this post


Link to post
Share on other sites
it's very trivial probelm. if you have two rect R1 = (x1min, y1min),(x1max, y1max) and R2 = (x2min, y2min), (x2max, y2max)

you simply check if the intersection of the intervals are empty or not

(x1min to x1max) UNION (x2min, x2max) MUST be non null and
(y1min to y1max) UNION (y2min, y2max) must also be non null(ie not empty)

this very simple concept translates into code as follows

if(x1min > x2max)
return false
if(x2min > x1max)
return false;

//and so for y
if(y1min > y2max)
return false
if(y2min > y1max)
return false

return true;


of course this only works for axis aligned rect..

Tim

Share this post


Link to post
Share on other sites
oops it seems I didn't look at grekster's post and posted the same solution. in any event, this shows the solution is correct.

Tim

Share this post


Link to post
Share on other sites
Quote:
Original post by mike74
My bad, grek. Looks good and seems to work.

mike
http://www.coolgroups.com/


hehe ok then, glad to have helped :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!