# rectangle-rectangle intersection

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

## 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 on other sites
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 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 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 grekstersomething 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 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 clbTake 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 on other sites
Quote:
 Original post by mike74I 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 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 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 on other sites
My bad, grek. Looks good and seems to work.

mike
http://www.coolgroups.com/

##### Share on other sites
Quote:
 Original post by mike74My bad, grek. Looks good and seems to work.mikehttp://www.coolgroups.com/

hehe ok then, glad to have helped :)

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633679
• Total Posts
3013294
×