File Exchange Pick of the Week

July 14th, 2008

Puzzler: Overlapping rectangles

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.

By Doug Hull

09:56 UTC | Posted in Puzzler | Permalink |

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

31 Responses to “Puzzler: Overlapping rectangles”

Doug replied on July 14th, 2008 at 09:57 UTC :

 
%% 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 July 14th, 2008 at 10:43 UTC :

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 July 14th, 2008 at 11:18 UTC :

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

DanK replied on July 14th, 2008 at 12:50 UTC :

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 July 14th, 2008 at 12:58 UTC :

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 July 14th, 2008 at 13:12 UTC :

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 July 14th, 2008 at 13:24 UTC :

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 July 14th, 2008 at 13:30 UTC :

 
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 July 14th, 2008 at 15:39 UTC :

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 July 14th, 2008 at 15:49 UTC :

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 July 14th, 2008 at 15:54 UTC :


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 July 14th, 2008 at 16:06 UTC :

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 July 14th, 2008 at 16:11 UTC :

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 July 14th, 2008 at 16:14 UTC :

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 July 14th, 2008 at 16:18 UTC :

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 July 14th, 2008 at 16:25 UTC :

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 July 14th, 2008 at 17:00 UTC :

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 July 14th, 2008 at 18:31 UTC :

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 July 14th, 2008 at 19:35 UTC :

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 July 14th, 2008 at 23:37 UTC :

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 July 15th, 2008 at 01:15 UTC :

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 July 15th, 2008 at 01:24 UTC :

… or …

 

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

Aigrette replied on July 15th, 2008 at 03:09 UTC :

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 July 15th, 2008 at 08:06 UTC :

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.
ArthurG replied on July 15th, 2008 at 08:12 UTC :

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 July 15th, 2008 at 10:26 UTC :

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

Quan Quach replied on July 15th, 2008 at 12:44 UTC :

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 Quach replied on July 15th, 2008 at 12:47 UTC :

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
Doug replied on July 15th, 2008 at 13:53 UTC :

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!

Quan Quach replied on July 15th, 2008 at 16:15 UTC :

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

Quan Quach replied on July 15th, 2008 at 16:16 UTC :

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

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.

Problems? Suggestions? Contact us at files@mathworks.com

Site Help
Patents
Trademarks
Privacy Policy
Preventing Piracy
RSS

File Exchange Pick of the Week

July 14th, 2008

Puzzler: Overlapping rectangles

31 Responses to “Puzzler: Overlapping rectangles”

Leave a Reply

About

Subscribe

Links

Categories

Recent Comments

Blog Admin

MATLAB Central Terms of Use