Re: Another graphical challenge...
Re: Another graphical challenge...
- Subject: Re: Another graphical challenge...
- From: Richard Kennaway <email@hidden>
- Date: Fri, 18 Apr 2008 13:42:36 +0100
Quoting Graham Cox <email@hidden>:
This is not really a Cocoa-specific problem, but before I embark on a
long-winded quest, I just wonder if there's a solution out there
already.
Given two rectangles that overlap in some way, I need to create a list
of all the rectangles that make up the non-overlapping areas. In other
words it's the exclusive-OR of the two inputs, but broken down into a
list of rects (preferably the smallest number needed to make up the
result).
It made an interesting lunchtime exercise! Here's one method, written
in Matlab because that's what was to hand, but it should be clear
enough how to write the same in any other language. The code finds
the part of a rectangle r1 outside a rectangle r2. Repeat with r1 and
r2 swapped to get the symmetric difference. The only division into
cases it needs is disjoint vs. non-disjoint.
% r1 and r2 are rectangles represented as 4-element vectors
% [ xlo, xhi, ylo, yhi ].
% The part of r1 outside r2 in general has 4 parts:
% +----------------------+
% r1 = | rt |
% | |
% |...+----+.............|
% |rl | r2 | rr |
% |...+----+.............|
% | |
% | rb |
% | |
% +----------------------+
% If r2 is not wholly inside r1 then one or more of the parts may be
% empty.
XLO = 1;
XHI = 2;
YLO = 3;
YHI = 4;
% Deal with the disjoint case first. This isn't entirely
necessary, as the
% code for the general case will give a correct answer in the
disjoint case,
% but it may unnecessarily split r1 into subrectangles.
if (r1(XLO) >= r2(XHI)) ...
|| (r1(XHI) <= r2(XLO)) ...
|| (r1(YLO) >= r2(YHI)) ...
|| (r1(YHI) <= r2(YLO))
% The rectangles are disjoint.
% Return r1 as the result.
return;
end
rightmostleft = max(r2(XHI),r1(XLO));
leftmostright = min(r2(XLO),r1(XHI));
upperlo = max(r2(YHI),r1(YLO));
lowerhi = min(r2(YLO),r1(YHI));
minYHI = min(r1(YHI),r2(YHI));
maxYLO = max(r1(YLO),r2(YLO));
% These are the four components of r1-r2. Return all the non-empty ones
% as the result.
rr = [ rightmostleft, r1(XHI), maxYLO, minYHI ];
rl = [ r1(XLO), leftmostright, maxYLO, minYHI ];
rt = [ r1(XLO), r1(XHI), upperlo, r1(YHI) ];
rb = [ r1(XLO), r1(XHI), r1(YLO), lowerhi ];
-- Richard Kennaway
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden