Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

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.

About these ads

13 Responses to “Rectangle Intersection – Find the Intersecting Rectangle”

  1. very good post from our team

  2. Mehmood said

    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 Nicholson said

    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 H said

    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.

  5. karlrado said

    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. [...] 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. Deepak said

    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. Hamsmooda said

    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. David said

    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. This post helped me a lot for my project. Thank you.

  11. 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.

  12. 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!

  13. very nice

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers

%d bloggers like this: