🔒 Locked

rectangle-rectangle intersection

Started by mike74 Aug 28, 2005 at 5:12 AM 9 replies 1k views

Original Post

154

Aug 28, 2005 at 5:12 AM

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/

clb

140

clb

Aug 28, 2005 at 5:22 AM

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.

grekster

Aug 28, 2005 at 5:31 AM

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.

mike74

Author

154

mike74

Aug 28, 2005 at 5:52 AM

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.

mike74

Author

154

mike74

Aug 28, 2005 at 5:55 AM

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.

grekster

Aug 28, 2005 at 5:58 AM

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?

timw

Aug 28, 2005 at 6:05 AM

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

timw

Aug 28, 2005 at 6:06 AM

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

mike74

Author

154

mike74

Aug 28, 2005 at 7:00 AM

My bad, grek. Looks good and seems to work.

mike
http://www.coolgroups.com/

grekster

Aug 28, 2005 at 7:02 AM

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 :)

Alrecenk

Aug 28, 2005 at 11:24 AM

I'm not entirely sure that it makes a difference, but it might be a tiny bit faster if you combine all the boolean expessions into 1 short circuitable one.

return !((x1min > x2max) || (x2min > x1max) || (y1min > y2max) || (y2min > y1max)) ;

Topic Locked

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