# Puzzler: Overlapping rectangles34

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

overlap = %1 for overlap, 0 for non-overlapping


<pre> <code>

all the code so someone can just copy and paste it from the comments.

</code> </pre>


Doug replied on : 1 of 34
 
%% Starting code

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

% Doug's solution
xVals = [ax' [0; 0]; bx' [1; 1]];
yVals = [ay' [0; 0]; by' [1; 1]];
%
% [0.1 0
%  0.6 0
%  0.5 1
%  0.9 1] % Example

xVals = sortrows(xVals,1);
yVals = sortrows(yVals,1);

%
% [0.1 0
%  0.5 1
%  0.6 0
%  0.9 1] % Example

xOverlap = ~isequal(xVals(1,2), xVals(2,2));
yOverlap = ~isequal(yVals(1,2), yVals(2,2));

% They are non-overlaping in a direction if the second column is
% [0 0 1 1]' or
% [1 1 0 0]'

overlap = xOverlap & yOverlap

% Must overlap in both directions to be overlaping.


Aigrette replied on : 2 of 34

My solution:

 
% define rectangle 1
x_rect1 = [ax(1) ax(2) ax(2) ax(1)];
y_rect1 = [ay(1) ay(1) ay(2) ay(2)];

%define rectangle2
x_rect2 = [bx(1) bx(2) bx(2) bx(1)];
y_rect2 = [by(1) by(1) by(2) by(2)];

% define all x and all y, and generate a grid of all possible combinations
all_x = [ax(1) ax(2) bx(1) bx(2)];
all_y = [ay(1) ay(2) by(1) by(2)];
[X,Y] = meshgrid(all_x, all_y);

% find which points are in which rectangle
in_rect1 = inpolygon(X,Y, x_rect1, y_rect1);
in_rect2 = inpolygon(X,Y, x_rect2, y_rect2);

% rectangle overlap if there is at least one point that is in both
% rectangles
overlap = any(in_rect1(:) & in_rect2(:))

 
Matt Whitaker replied on : 3 of 34

A bit of a Java cheat but:

 
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

r = javaObject('java.awt.geom.Rectangle2D$Double',ax(1),ay(1),diff(ax),diff(ay)); overlap = r.intersects(bx(1),by(1),diff(bx),diff(by))   DanK replied on : 4 of 34 Here’s my version, not pretty, but it should be hard to beat on speed. (disp is optional).  if bx(1)>ax(2)||by(1)>ay(2)||bx(2)<ax(1)||by(2)<ay(1) overlap = 0 else overlap =1 end  Tahim replied on : 5 of 34 Far away from a good solution, but it works!   %It verifies if exist an axis from 'bx' between the 'ax' (axesBXIsBetweenAX) %and if exist an axis from 'by' between 'ay' (axesBYIsBetweenAY); axesBXIsBetweenAX = (bx(1) > ax(1) && bx(1) ax(1) && bx(2) ax(1) && bx(2) ay(1) && by(1) ay(1) && by(2) ay(1) && by(2) by(1)) && (ay(2) bx(1)) && (ax(2) < bx(2)); Overlap = (axesBXIsBetweenAX && axesBYIsBetweenAY) ||... (axesBXIsBetweenAX && specialCaseAy) ||... (axesBYIsBetweenAY && specialCaseAx) ||... (specialCaseAy && specialCaseAx); if Overlap display('Overlap'); else display('No overlap'); end   Tahim replied on : 6 of 34 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. Tahim replied on : 7 of 34 One more try!   %It verifies if exist an axis from 'bx' between the 'ax' (axesBXIsBetweenAX) %and if exist an axis from 'by' between 'ay' (axesBYIsBetweenAY); axesBXIsBetweenAX = (bx(1)>ax(1) && bx(1)ax(1) && bx(2)ax(1) && bx(2)ay(1) && by(1)ay(1) && by(2)ay(1) && by(2)by(1)) && (ay(2)bx(1)) && (ax(2)<bx(2)); Overlap = (axesBXIsBetweenAX && axesBYIsBetweenAY) ||... (axesBXIsBetweenAX && specialCaseAy) ||... (axesBYIsBetweenAY && specialCaseAx) ||... (specialCaseAy && specialCaseAx); if Overlap display('Overlap'); else display('No overlap'); end   matt fig replied on : 8 of 34   tf1 = ax(1)>bx; tf2 = ax(2)>bx; tf3 = ay(1)>by; tf4 = ay(2)>by; sm = sum([[tf1 tf2];[tf3 tf4]],2); if ~any(sm == 0 |sm == 4) overlap = 1 else overlap = 0 end   ArthurG replied on : 9 of 34 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:  % Adjacent rectangles, identified as non-overlapping ax = [1 2]; ay = [1 2]; bx = [2 3]; by = [1 2]; overlapDoug(ax,ay,bx,by) % == 0 %Swapping identifies them as overlapping overlapDoug(bx,by,ax,ay) % == 1  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… ArthurG replied on : 10 of 34 function overlap = overlapArthur(ax,ay,bx,by) % Put coordinates into a matrix, each column is a rectangle X = [ax(:) bx(:)]; Y = [ay(:) by(:)]; % Segments overlap if maxmin < minmax % Segments are adjacent if maxmin == minmax % Segments don't overlap if maxmin > minmax % where % maxmin = the right-most left edge % minmax = the left-most right edge % % Overlap example: % ax(1)--------ax(2) % bx(1)----------bx(2) % % X = [ax(1) bx(1); ax(2) bx(2)] % min(X) == [ax(1) bx(1)] % max(X) == [ax(2) bx(2)] % max(min) == bx(1) % min(max) == ax(2) % bx(1) < ax(2) ==> segments overlap overlapFunc = @(c) max(min(c)) < min(max(c)); % For a rectangle, both X and Y must overlap overlap = overlapFunc(X) & overlapFunc(Y); ArthurG replied on : 11 of 34  function tests = overlap_tests(fh) % overlap_tests(fh) applies a series of tests to a function fh where % overlap = fh(ax,ay,bx,by) % the rectangles and coordinates are permuted to see if the % function correctly handles equivalent cases % non-overlapping in both dimensions tests = struct('ax',[1 2], 'ay', [1 2], 'bx', [3 4], 'by', [3 4], 'expected_result', 0, 'actual_result', []); % overlap in in one dimension but not both tests(2) = struct('ax',[1 2], 'ay', [1 4], 'bx', [3 4], 'by', [2 3], 'expected_result', 0, 'actual_result', []); % one rectangle inside the other tests(3) = struct('ax',[1 4], 'ay', [1 4], 'bx', [2 3], 'by', [2 3], 'expected_result', 1, 'actual_result', []); % same rectangle tests(4) = struct('ax',[1 2], 'ay', [1 2], 'bx', [1 2], 'by', [1 2], 'expected_result', 1, 'actual_result', []); % adjacent rectangles tests(5) = struct('ax',[1 2], 'ay', [1 2], 'bx', [2 3], 'by', [1 2], 'expected_result', 0, 'actual_result', []); % overlapping rectangles, same y-dimensions tests(6) = struct('ax',[1 3], 'ay', [1 3], 'bx', [2 4], 'by', [1 3], 'expected_result', 1, 'actual_result', []); % overlapping, y-dimension completely contained tests(7) = struct('ax',[1 3], 'ay', [1 4], 'bx', [2 4], 'by', [2 3], 'expected_result', 1, 'actual_result', []); % overlapping corners tests(8) = struct('ax',[1 3], 'ay', [1 3], 'bx', [2 4], 'by', [2 4], 'expected_result', 1, 'actual_result', []); for i=1:numel(tests) tests(i).actual_result = run_tests(tests(i), fh); tests(i).failed = find(tests(i).actual_result ~= tests(i).expected_result); end end % function overlap_tests function result = run_tests(test, fh) % consider equivalent permutations of inputs result = zeros(1,2^6); idx = 0; for i1=1:2 t = test; if i1==2 % swap a & b [t.ax, t.ay, t.bx, t.by] = deal(t.bx, t.by, t.ax, t.ay); end for i2=1:2 if i2==2 % swap x & y [t.ax, t.ay, t.bx, t.by] = deal(t.ay, t.ax, t.by, t.bx); end for i3=1:2 if i3==2 % swap a's x ordering t.ax = t.ax(end:-1:1); end for i4=1:2 if i4==2 % swab a's y ordering t.ay = t.ay(end:-1:1); end for i5=1:2 if i5==2 % swap b's x ordering t.bx = t.bx(end:-1:1); end for i6=1:2 if i6==2 % swap b's y ordering t.by = t.by(end:-1:1); end idx = idx+1; result(idx) = fh(t.ax, t.ay, t.bx, t.by); end end end end end end end % function run_tests  DanK replied on : 12 of 34 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

Doug replied on : 13 of 34

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

Doug replied on : 14 of 34

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

matt fig replied on : 15 of 34

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:

 

sm = sum([[ax(1)>bx ax(2)>bx];[ay(1)>by ay(1)>by]],2);
if any(sm == 0 | sm == 4)
overlap = 0
else
overlap = 1
end

 
matt fig replied on : 16 of 34

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.

ArthurG replied on : 17 of 34

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

[ax,ay,bx,by] = deal([0 0]);

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

matt fig replied on : 18 of 34

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.

 
axr = diff(ax); % length of the rectangle's sides.
ayr = diff(ay);
bxr = diff(bx);
byr = diff(by);
xr = axr+bxr; % minumum distance for them to not overlap
yr = ayr+byr;
xvct = [bx,ax]; % vectors of coords.
yvct = [by,ay];
outerdiffx = abs(max(xvct))-abs(min(xvct));
outerdiffy = abs(max(yvct))-abs(min(yvct));

if outerdiffx<xr && outerdiffy<yr
overlap = 1
else
overlap = 0
end
 
ArthurG replied on : 19 of 34

Matt,

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


axr = abs(diff(ax)); % length of the rectangle's sides.
ayr = abs(diff(ay));
bxr = abs(diff(bx));
byr = abs(diff(by));
xr = axr+bxr; % minumum distance for them to not overlap
yr = ayr+byr;
xvct = [bx,ax]; % vectors of coords.
yvct = [by,ay];
outerdiffx = max(xvct)-min(xvct);
outerdiffy = max(yvct)-min(yvct);

overlap = outerdiffx<xr && outerdiffy<yr;

matt fig replied on : 20 of 34

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!

 
axr = diff(ax); % length of the rectangle's sides.
ayr = diff(ay);
bxr = diff(bx);
byr = diff(by);
xr = axr + bxr; % minumum distance for them to not overlap
yr = ayr + byr;
xvct = [bx, ax]; % vectors of coords.
yvct = [by, ay];
outerdiffx = max(xvct) - min(xvct);
outerdiffy = max(yvct) - min(yvct);

overlap = outerdiffx<xr && outerdiffy<yr;

 
Andreas replied on : 21 of 34

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

 
overlap = ~ ((ax(1) > bx(2) | bx(1) > ax(2)) | (ay(1) > by(2) | by(1) > ay(2)));
 
Andreas replied on : 22 of 34

… or …

 
voverlap =  (ax(1) < bx(2) & bx(1) < ax(2)) & (ay(1) < by(2) & by(1) < ay(2));


Aigrette replied on : 23 of 34

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

 

% define rectangle 1
rect1 = [ax(1) ay(1) diff(ax) diff(ay)];

% define rectangle 2
rect2 = [bx(1) by(1) diff(bx) diff(by)];

% the lazy solution
overlap = (rectint(rect1,rect2)~=0)

 
Roy replied on : 24 of 34

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

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.

ArthurG replied on : 25 of 34

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.

Doug replied on : 26 of 34

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:



if min(ay) > min(by)
temp = ay;
temp2 = ax;
ay = by;
ax = bx;
by = temp;
bx = temp;
%swapping rectangle coordinates. too lazy to explain why
end

if max(ax) = max(bx)
overlap = 0;
elseif max(ay) >min(by)
overlap = 1;
else
overlap = 0;
end


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!

Doug replied on : 29 of 34

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:



if min(ay) > min(by)
temp = ay;
temp2 = ax;
ay = by;
ax = bx;
by = temp;
bx = temp;
%swapping rectangle coordinates. too lazy to explain why
end

if max(ax) =max(bx)
overlap = 0;
elseif max(ay) >min(by)
overlap = 1;
else
overlap = 0;
end



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

red replied on : 32 of 34

if( ((bx1 >= ax1 && bx1 <= ax2) || (bx2 >= ax1 && bx2 <= ax2)) && ((by1 >= ay1 && by1 <= ay2) || (by2 >= ay1 && by2 <= ay2)))
overlap = 1;
else
overlap = 0;

end

matt fig replied on : 33 of 34

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.

 
A = abs(by(1)+by(2)-ay(1)-ay(2));
B = abs(bx(1)+bx(2)-ax(1)-ax(2));
C = ay(2)-ay(1)+by(2)-by(1);
D = ax(2)-ax(1)+bx(2)-bx(1);

if A*D < B*C
Overlap = B < D;
else
Overlap = A < C;
end
 
Utkarsh replied on : 34 of 34

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

What is 3 + 5?

Preview: hide

These postings are the author's and don't necessarily represent the opinions of MathWorks.