Doug's MATLAB Video Tutorials

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:

puzzlerrect.jpg

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

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

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(:))

 

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

%your code here
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))

 

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

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

 

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!

 

%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
 
 
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
 

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…

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);

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

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:

 

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

 

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:

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

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
 

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;

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;

 

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)));
 

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)

 

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:




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!

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

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.

 
    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
 

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

Add A Comment

What is 3 + 4?

Preview: hide

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