Technical Interview Questions

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

Archive for October 12th, 2006

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.

Advertisements

Posted in Algorithms, C++, General, Graphics, Microsoft, Progamming Languages | 14 Comments »