Q: Rectangle Intersection - Find the Intersecting Rectangle
In the last post, we looked into methods to determine whether or not two given rectangles intersect each other. Lets go one step ahead this time and find the intersecting rectangle.
As in the previous post, I am 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.
bool Intersect(RECT* r3, const RECT * r1, const RECT * r2)
{
bool fIntersect = ! ( r2->left > r1->right
|| r2->right < r1->left
|| r2->top > r1->bottom
|| r2->bottom < r1->top
);
if(fIntersect)
{
SetRect(r3,
max(r1->left, r2->left),
max(r1->top, r2->top),
min( r1->right, r2->right),
min(r1->bottom, r2->bottom));
}
else
{
SetRect(r3, 0, 0, 0, 0);
}
return fIntersect;
}
First, determine whether or not the two Rectangles intersect each other, Then use the SetRect method (which basically creates a RECT with the given points) and create the intersecting Rectangle
SetRect(r3,
max(r1->left, r2->left),
max(r1->top, r2->top),
min( r1->right, r2->right),
min(r1->bottom, r2->bottom));
Since the algorithm is pretty straightforward, I am not going to include more detailed analysis in this post, unless I get enough request comments or email :)
NOTE: For all invalid rectangles passed to the function, the return value is always [0,0,0,0]. You can also choose to return error codes after checking for validity.
Comments
[...] The calculation is
[...] The calculation is simple: find if two Rectangles overlap or intersects; this is done through checking their boundaries. I’ve found this page: http://www.tekpool.com/?p=24 which show the calculation. As I had to do it in MySQL (for a simple problem otherwise I will be using MySQL GIS extensions =) ) I’d rewrite the calculation using De Morgan Laws for a better code. [...]
Craig, I have based the
Craig,
I have based 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. The algorithm you mentioned, will work with the origin is at the lower left corner and the Y axis moves towards the top.
Hi you have a slight typo
Hi
you have a slight typo in your code shouldn't
bool fIntersect = ( r2->left right
&& r2->right > r1->left
&& r2->top bottom
&& r2->bottom > r1->top
);
be....
bool fIntersect = ( r2->left right
&& r2->right > r1->left
&& r2->top > r1->bottom
&& r2->bottom top
);
with the last two greater / less than's the other way around.
/craig
(condition1 || condition2 ||
(condition1 || condition2 || condition3 || condition4) is equivalent to !(condition1 && condition2 && condition3 && condition4)
Also, this method has been tested against GDI's IntersectRect (http://msdn.microsoft.com/library/default.asp?url=/library/en-us/gdi/rec...)
You changed the rectangle
You changed the rectangle intersect test from your previous post, and I don't think it's equivalent. For example, what if r1 had a left of 5 and right of 10, and r2 had a left of 0 and a right of 3. The first condition in your test would be true even though the two rectangles could not intersect.