# Technical Interview Questions

• ## Blog Stats

• 442,076 hits

## Rectangle Intersection – Find the Intersecting Rectangle

Posted by tekpool on October 12, 2006

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 right && r2->right > r1->left && r2->top 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.

1. ### swissreplica6said

very good post from our team

2. ### Mehmoodsaid

Hey thats great and never thought it so simple.. ‘coz i was thinking of some hidden surface removal algorithm .. OUCH !!! anyway thanks for such a wonderful post..

3. ### Tim Nicholsonsaid

What this is missing is the case where the second rectangle is wholly contained within the first. The above returns the coordinates of the larger of the two rectangles, but in most clipping cases, it would be the coordinates of the smaller rectangle that would be of interest. This is easy to fix and would make a more useful function for graphic clipping applications.

4. ### Chris Hsaid

This algorithm is broken. Imagine two squares whose intersection is a small square in the upper right of one of the squares. This algorithm will choose the max left (upper square), max top (upper square), min right (lower square) and min bottom (lower square) giving a rectangle that stretches from the bottom of the lower square all the way to the top of the upper square.

It also misses the case Tim Nicholson points out where one rectangle completely covers the second rectangle.

I think that Chris H is forgetting that the y axis is increasing in a downwards direction in Windows. http://www.functionx.com/visualc/gdi/gdicoord.htm

6. ### Best Webfoot Forward » Programming persistencesaid

[…] When it came time to implement my polygon bounding box intersection code again, I looked at my old polygon intersection code again, saw that it took eight comparisons, and thought to myself, “That can’t be right!”  Indeed, it took me very little time to come up with a version with only four comparisons, (and was now able to find sources on the Web that describe that algorithm). […]

7. ### Deepaksaid

Hey,
Ive made a program that would be of some useful reference to you guys. Please see the following link to get the C code to find intresecting rectangles. It uses a tree datastructure and the efficiency is good.
http://myexps.blogspot.com/2009/11/rectangle-intersection-with-tree.html

8. ### Hamsmoodasaid

A Seattle Transferral Fix up and Overhaul Against dedicated to transference into working order and rebuilding, Snag a grasp at Service, Engine Revamping, Rear Extinguish Adjustment, 4X4 Improvement, Steer line Repair, Chic Moving, Euphemistic pre-owned Transporting, Forwarding parts and more..

transmission seattle

9. ### Davidsaid

Just checked the cases, very good one, did not found cases where it wouldnt fit. Have been thinking about coming to the silliest ideas but this one does it at a pretty simple way 🙂

10. ### Mark Johnsonsaid

This post helped me a lot for my project. Thank you.

11. ### discount eurail passessaid

You would not hear him performing You Never Know” to your instrumental Laffy Taffy” If you havent heard You Never
Know, take off listen to it). However, in order to
create your own demo CD, you will need to put in some effort as it will
be a source of your introduction to the independent record
labels. The Internet is a global marketplace and your beat buyer could come from anywhere.

Hello! I know this is kinda off topic but I was wondering if
you knew where I could get a captcha plugin for my comment
form? I’m using the same blog platform as yours and I’m having trouble finding
one? Thanks a lot!

very nice

14. ### MichaelVeksaid

wh0cd402083 furosemide 12.5 mg