Rectangle Intersection – Determine if two given rectangles intersect each other or not
Posted by tekpool on October 11, 2006
Q: Rectangle Intersection: Determine if two given rectangles intersect each other or not
Definitions:
Intersect: Two Rectangles intersect each other if the share a common area.
Assumptions:
- Both the rectangles are aligned with the x and y axes.
- Rectangles just touching each other are considered as non-intersecting.
First let’s create a data structure for use in our problem. Rectangle Intersection algorithms are usually used in graphics problems. Depending on the precision needed to represent the co-ordinates, you may choose the required data type. In this case, I am going to use a LONG.
I am also basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.
struct { LONG left; LONG top; LONG right; LONG bottom; } RECT; bool IntersectRect(const RECT * r1, const RECT * r2) { return ! ( r2->left > r1->right || r2->right left || r2->top > r1->bottom || r2->bottom top ); }
The above algorithm finds the conditions at which the rectangles do not intersect and then negates the values to get the result. There is a straight forward way of doing the same algorithm, but it requires far more conditions than the one above. Consider the diagram below
S1 | S2 | S3 | | TOP|LEFT | ----------------------------------- | | | | | | S4 | S5 | S6 | | | | ----------------------------------- | RIGHT|BOTTOM | | S7 | S8 | S9
This is an illustration of one of the rectangles (R1). The top left corner of R2 can like in any of the 9 segments, S1 through S9. Based on each of these cases, and depending on the position of the other vertices, it can be determined whether the two rectangles R1 and R2 intersect each other. E.g. If R2’s top left corner is in S1, the bottom right corner needs to be in S5 or beyond (S5,S6,S8,S9) for the rectangles to intersect. Or if the top left corner of R2 is in S5, it is an automatic case of intersection. Clearly, in this case there are a lot of cases to consider and therefore and lot of conditions to check.
The conditions where the rectangles do not intersect, is where the bounds of one Rectangle is beyond the bounds of the other. The conditions are pretty straightforward as shown in the code above. Negating this value solves the original problem.
There is one more conditions (negation) that can be avoided by changing the inner condition. I will leave that as an exercise for the reader.
NOTE: For all invalid rectangles passed to the function, the return value is always false. You can also choose to return error codes after checking for validity.
Kyle said
Thanks! I assigned each condition a variable name (above, below, left, and right). The resulting final condition in pretty (in ruby at least):
not above and not below and not left and not right
It’s intuitive: If touching, it will not be above, below, to the right, or to the left!
Determining If Rectangles Intersect? : : JasonJackson.com said
[…] own and immediatly had a very nasty chunk of code. I knew I was doing something wrong. I found this short article which immediatly made me think back to college CompSci with its simple solution. I need to test […]
ADHAR said
i did not understand the second and the fourth conditions in the conditional expression i.e r2->right left and r2->bottom top.can you please help me with this.
leek said
The WordPress comment parser stripped out the < r1->, figuring it to be an HTML tag.
return ! ( r2->left > r1->right
|| r2->right < r1->left
|| r2->top > r1->bottom
|| r2->bottom < r1->top
);
Al said
Not sure if this is the most effective but it has suited my purpose: find the bounding box and see if the sides are bigger than the 2 rectangles touching at 2 corners if you get my drift:
private boolean overlap(int sx1, int sy1, int w1, int h1,
int sx2, int sy2, int w2, int h2)
{
int leastx, leasty, mostx, mosty ;
if ( sx1 < sx2 ) { leastx = sx1; mostx = sx2; }
else { leastx = sx2; mostx = sx1; }
if ( sy1 ( w1 + w2 ) ) return false ;
if ( ( mosty – leasty ) > ( h1 + h2 ) ) return false ;
return true;
}
Al said
Whoa… lets try that again… formatting issues…
private boolean overlap(int sx1, int sy1, int w1, int h1,
int sx2, int sy2, int w2, int h2)
{
int leastx, leasty, mostx, mosty ;
if ( sx1 < sx2 ) { leastx = sx1; mostx = sx2; }
else { leastx = sx2; mostx = sx1; }
if ( sy1 ( w1 + w2 ) ) return false ;
if ( ( mosty - leasty ) > ( h1 + h2 ) ) return false ;
return true;
}
Al said
Ok, something is stripping out half my code…
Al said
Ok one more time. The scripts keep thinking that LT and GT symbols are tags even in preformatted text. Talk about overkill!
Sigh.
Jo said
Hi Al,
good idead, but propably you missed some values (h1,h2,w1,w2) to integrate into your calculations when trying to find mostx, mosty:
private boolean overlap(int sx1, int sy1, int w1, int h1,
int sx2, int sy2, int w2, int h2)
{
int leastx, leasty, mostx, mosty;
if (sx1 LESSTHAN sx2)
{
leastx = sx1;
mostx = sx2 + w2;
}
else
{
leastx = sx2;
mostx = sx1 + w1;
}
if (sy1 LESSTHAN sy2)
{
leasty = sy1;
mosty = sy2 + h2;
}
else
{
leasty = sy2;
mosty = sy1 + h1;
}
if ((mostx – leastx) GREATERTHAN (w1 + w2)) return false;
if ((mosty – leasty) GREATERTHAN (h1 + h2)) return false;
return true;
}
гей знакомства bluesystem said
итак: неподражаемо…
persick said
AS3 code:
public class Rect
{
public var x1: Number, y1: Number;
public var x2: Number, y2: Number;
…..
}
function intersect(r1:Rect, r2:Rect)
{
var on_x: Boolean = (r2.x1 >= r1.x1 && r2.x1 = r2.x1 && r1.x1 = r1.y1 && r2.y1 = r2.y1 && r1.y1 <= r2.y2);
return on_x && on_y;
}
persick said
buggy comment display 😦
Hein Thet said
This was one of the interview exam i took yesterday..! got it sorted out, but in slightly different way.
Az said
Why negate?
The intersect condition is much simpler than how you have expressed in those 9 segments. There are really only 2 “segments” and you only need to check for one corner in each.
It is simple:
IF
TOPLEFT is in S1 || S2 || S4 || S5
AND
BOTTOMRIGHT is in S5 || S6 || S8 || S9
then you have intersecting rectangles.
The code has the same number of conditions as what the blog example has:
r2->Right > r1->Left &&
r2->Bottom Top &&
r2->Top > r1->Right &&
r2->Left Bottom
BMX said
That doesn’t handle the crossing case for two rectangles. Corners need not be contained within the bounds of the other rectangle for an intersection to occur.
Az said
Az said
Az said
r2->Right > r1->Left &&
r2->Bottom < r1->Top &&
r2->Top > r1->Bottom &&
r2->Left < r1->Right
Let’s build an HTML5 game! (Beginner Tutorial, Part 2) | Web App List: Showcasing the best web apps said
[…] Now, step two: Check to see if our bullet resides within the bounds of each enemy. Here we need a little math: […]
What is the fastest way to work out 2D bounding box intersection? | DL-UAT said
[…] The original function – and an alternative description of why it works – can be found here: https://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-int… […]
Garland Rolla said
Hello friends, its fantastic paragraph concerning educationand fully explained, keep it up all the time.|
BrookSmall said
I have checked your site and i have found some duplicate content,
that’s why you don’t rank high in google, but there is a tool that can help you to create 100% unique content,
search for; Boorfe’s tips unlimited content