Finding If Two Rectangles Are Overlapped

Here is another popular interview questions: given two rectangles, each represented by two points: an upper left (UL) and a lower right (LR) corner. Write a function that takes in two rectangles and return true if they are overlapped, false if they are not.

Before we start coding, let’s take a look of the cases where rectangles are overlapped, and cases where they are not:


Based on my readings and experience, it is much simpler to determine if rectangles are not overlapped than if they are: we only have four cases to consider, and each case, we only need one comparison. In contrary, the four cases where the rectangles do overlapped are complex because we need to make several comparisons in each case. Therefore, our function will determine if the rectangles are not overlapped, then negate the result.

Before we go on, we need to take a step back and study the coordinate system used in most computer graphics frameworks. In most system, the origin (x = 0, y = 0) is located at the top left corner of the screen with he X axis extents from left to right and the Y axis from top to bottom.

So, how do we determine if the two rectangles are not overlapped? There are really four cases:

Case 1: A is to the left of B. In this case A’s right edge is either to the left of or touch B’s left edge. In the expression below, UL is short for upper left, and LR is for lower right. We can express this case in code as follow:

a.lr.x <= b.ul.x

Case 2: A is to the right of B:

a.ul.x >= b.lr.x

Case 3: A is above B:

a.lr.y <= b.ul.y

Case 4: A is below B:

a.ul.y >= b.lr.y

Putting these cases together and negate them, we got the conditions where the two rectangles overlap:

!(a.lr.x <= b.ul.x || 
a.ul.x >= b.lr.x || 
a.lr.y <= b.ul.y || 
a.ul.y >= b.lr.y)

As you can recall from your logic class: !(a || b) is the same as (!a && !b). Therefore, we can rewrite the above expression as:

a.lr.x > b.ul.x && 
a.ul.x < b.lr.x && 
a.lr.y > b.ul.y && 
a.ul.y < b.lr.y[/sourcecode]

And that will be the expression to test if two rectangles are overlapped.

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