Re: Another graphical challenge...
Re: Another graphical challenge...
- Subject: Re: Another graphical challenge...
- From: Graham Cox <email@hidden>
- Date: Sat, 19 Apr 2008 00:28:14 +1000
Richard, thanks very much for applying yourself to this problem. You
make it seem easy, and it works a treat. I obviously haven't drunk
enough coffee today as it looked a lot harder than it turned out to be!
Here's my ready-to-use Cocoa-conversion, if anyone else wants to make
use of it.
NSSet* DifferenceOfTwoRects( const NSRect a, const NSRect b )
{
NSMutableSet* result = [NSMutableSet set];
// if a == b, there is no difference, so return the empty set
if( ! NSEqualRects( a, b ))
{
NSRect ir = NSIntersectionRect( a, b );
if( NSEqualRects( ir, NSZeroRect ))
{
// no intersection, so result is the two input rects
[result addObject:[NSValue valueWithRect:a]];
[result addObject:[NSValue valueWithRect:b]];
}
else
{
// a and b do intersect, so collect all the pieces by subtracting
<ir> from each
[result unionSet:SubtractTwoRects( a, ir )];
[result unionSet:SubtractTwoRects( b, ir )];
}
}
return result;
}
NSSet* SubtractTwoRects( const NSRect a, const NSRect b )
{
// subtracts <b> from <a>, returning the pieces left over. If a and b
don't intersect the result is correct
// but maybe broken into pieces when it doesn't need to be, so the
caller should test for intersection first.
NSMutableSet* result = [NSMutableSet set];
float rml, lmr, upb, lwt, mny, mxy;
rml = MAX( NSMaxX( b ), NSMinX( a ));
lmr = MIN( NSMinX( b ), NSMaxX( a ));
upb = MAX( NSMaxY( b ), NSMinY( a ));
lwt = MIN( NSMinY( b ), NSMaxY( a ));
mny = MIN( NSMaxY( a ), NSMaxY( b ));
mxy = MAX( NSMinY( a ), NSMinY( b ));
NSRect rr, rl, rt, rb;
rr = NSMakeRect( rml, mxy, NSMaxX( a ) - rml, mny - mxy );
rl = NSMakeRect( NSMinX( a ), mxy, lmr - NSMinX( a ), mny - mxy );
rt = NSMakeRect( NSMinX( a ), upb, NSWidth( a ), NSMaxY( a ) - upb );
rb = NSMakeRect( NSMinX( a ), NSMinY( a ), NSWidth( a ), lwt -
NSMinY( a ));
// add any non empty rects to the result
if ( rr.size.width > 0 && rr.size.height > 0 )
[result addObject:[NSValue valueWithRect:rr]];
if ( rl.size.width > 0 && rl.size.height > 0 )
[result addObject:[NSValue valueWithRect:rl]];
if ( rt.size.width > 0 && rt.size.height > 0 )
[result addObject:[NSValue valueWithRect:rt]];
if ( rb.size.width > 0 && rb.size.height > 0 )
[result addObject:[NSValue valueWithRect:rb]];
return result;
}
On 18 Apr 2008, at 10:42 pm, Richard Kennaway wrote:
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
_______________________________________________
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