# Puzzler: Overlapping rectangles 34

Posted by **Doug Hull**,

Today’s challenge is one where you need to figure out if two rectangles have a non-zero area of overlap.

The rectangles will be specified as follows:

Just fill in your part of the code until you get the binary variable overlap defined.

```
ax = sort(rand(1,2));
ay = sort(rand(1,2));
bx = sort(rand(1,2));
by = sort(rand(1,2));
clf
rectangle('position',[ax(1) ay(1) diff(ax) diff(ay)], 'edgecolor', 'r')
hold on
rectangle('position',[bx(1) by(1) diff(bx) diff(by)], 'edgecolor', 'k')
axis equal
%your code here
overlap = %1 for overlap, 0 for non-overlapping
```

When you post your code in the comments, please use the tags

```
<pre> <code>
all the code so someone can just copy and paste it from the comments.
</code> </pre>
```

My solution is already posted.

## 34 CommentsOldest to Newest

My solution:

A bit of a Java cheat but:

Here’s my version, not pretty, but it should be hard to beat on speed. (disp is optional).

Far away from a good solution, but it works!

Sorry about my post, I don’t know how to fix it. I am afraid to post it one more time and get it messy again.

Very good solution Dank… I just went in the wrong way!! I put the conditions that would make two rectangles overlap.

One more try!

Hmm… This is trickier than people think. I wrote test cases and tested the solutions that I could get to run, and it seems all the solutions so far fail in a few cases. [Doug, maybe you should run a story about unit testing and testing frameworks for MATLAB?] The most common failure is when the two rectangles are ADJACENT but not overlapping. All the solutions so far (including Doug’s) have a hard time with this case. What’s weird, is that swapping rectangle A and rectangle B will change whether they are considered overlapping or not.

Picking on Doug for a minute:

I haven’t taken the time to figure out why the logic fails, and why the order matters though. I’ll post my code and my test suite in separate comments…

Arthur,

Kudos on being diligent, but the case of adjacent rectangles was never part of the challenge. The goal was to identify cases of non-zero overlapped area. In cases of adjacentcy, the overlap area is zero.

Just my $0.02

Dan

Arthur,

I was wondering if someone would find the hole in my armor before I went home for the evening!

Yes, I do have a flaw in the algorithm. Yes, I knew about it before I posted. Kind of a meta-challenge! Next time I should post that there is an edge case that fails.

What is going on is that I sort the four x-coordinates and check to see if two coordinates from the two rectangles stay together after the sort. Works pretty clean when they are non-adjacent. Avoids a lot of convoluted logic.

So why does it give different answers for different orders of inputs? Well, I am using SORTROWS, and if the two coordinates are the same because of adjacent rectangles, it is arbitrary which row is first. MATLAB leaves them in their original order (as it says in the documentation). Depending on the order that the rectangles were put in the function, this will make it appear their is interleaving or not.

Checking for this adjacent rectangle case would cause a lot of the convoluted logic tests. These are the tests that I was trying to avoid. I should have used danK’s solution. It is the cleanest and easiest to understand.

Actually, I could run the algorithm twice with reversed inputs, but that seems like a kludge.

Proper unit testing would have caught this logical error. For these challenges, I have been relying on random inputs to flush out most of the errors, but sometimes, you just need to hand write tests that put in cases you know are going to be tricky.

Thanks for the excellent catch. E-mail me the postal address and t-shirt size. I will get something out to you soon!

-Doug

Dan,

Arthur did catch me because my solution gives two different outputs for the same two rectangles. One must be wrong.

I was caught, fair and square!

Doug

To ArhurG,

My solution says the adjacent rectangles aren’t overlapped whether a is on the left or right, or did I misunderstand your post? Here is my solution reprinted with simplifications:

Please ignore the simplifications in my last post, I made a mistake! It seems my original solution DOES say the rectangles are overlapped when a is on the right.

BTW, I just thought of another edge-case where code might fail: identical zero-area rectangles:

Thinking about the actual problem statement, our solutions are a bit abstracted from the original statement that the overlapping area must be non-zero. If you had told us to write a function that calculates the overlapping area, I think we’d be a lot more likely to catch our mistakes. This “simpler” problem is actually “harder.”

O.k., second try. For some odd reason this is an interesting problem to me… I think this works for the adjacent cases as well as when just the corners are touching.

Matt,

You’ve almost got it… You just need to change where you use abs. I believe this fixes your code:

ArthurG,

Nice trick getting rid of the if-else in my code, I will have to remember that one. Actually, I don’t believe the abs is necessary at all, since ax, ay, bx and by are sorted on declaration, at least in the original problem statement!

I didn’t read through all sumbissions so something like that may have already been posted. Is there anything wrong with the obvious solution?

… or …

Alright, I think I have found the laziest solution. I should have lookfored “area” earlier…

There is a File Exchange submission by Doug Schwarz to compute the intersections of two piecewise-linear curves here:

http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=11837&objectType=file

For each pair of line segments, the linear algebra to determine their intersection point is of course easy put expensive, so the code first checks to see if the smallest rectangles enclosing them overlap. See lines 99-109 of the code.

Aigrette, I like that your solution uses the actual rectangle area.

Doug never specifically said whether the coordinates are sorted. Note that most of the posted solutions will fail if they aren’t.

Aigrette,

I did not know about that function, that is easy and clean. I like seeing how many different solutions there are for these very simple problems. It helps us all run into new techniques and functions.

Thanks all!

Doug

I think I’ll give this a try:

Man, that was a lot of work! Do I win a prize if my submission passes the stress test? My old MATLAB t-shirt is getting worn down from wearing it so much. Need new one!

I hate you for wasting my time on these puzzlers. See blinkdagger post please, I have a recommendation for you!

http://www.blinkdagger.com/blog/mathematical-body-art

Quan,

That did not seem to work, may have gotten garbled a bit since the first if statement has an assignment where it should have a ==.

Doug

PS. You are welcome for the puzzles!

Okay, trying again:

Looks like it doesn’t like my “or” symbol. Now we will never know if I solved your puzzler :(

if( ((bx1 >= ax1 && bx1 <= ax2) || (bx2 >= ax1 && bx2 <= ax2)) && ((by1 >= ay1 && by1 <= ay2) || (by2 >= ay1 && by2 <= ay2)))

overlap = 1;

else

overlap = 0;

end

O.k., so I am finally taking a class in C++, and this very problem was assigned. I knew I could come back here and use one of the solutions, but I decided to try a different approach. The method I found is very fast, I think because there are only two comparisons. Here it is.

if(ax(1) > bx(1))

tempx=ax;

tempy=ay;

ax=bx;

ay=by;

bx=tempx;

by=tempy;

end

overlap=0;

if(ax(1) < bx(1)&&bx(1) < ax(2))

if(ay(1) < by(1)&&by(1) < ay(2))

overlap=1

end

if(ay(1) < by(2)&&by(2) < ay(2))

overlap=1;

end

if(ay(1) by(2))

overlap=1;

end

if(ay(1) > by(1)&&ay(2) < by(2))

overlap=1;

end

end

overlap