On Jun 8, 2012, at 4:01 AM, Gregory Weston wrote:
> Strictly what I need is the set of individual line segments that define the
> perimeter, but I figured that it anyone had a solution to the problem in
> already it was likely to be giving back a path instead of just a list of
> points and I could parse the path.
That's actually an easier problem. Assembling the line segments back into a
*continuous* path might take some work, perhaps best left as an exercise for
the student.
Make a set of points, consisting of the four corners of each display. To handle
mirrored displays, discard all four points for a display that has the same
topLeft as a previous display. (Or see the generalization below that allows for
arbitrary overlap between displays.)
To get the horizontal line segments, sort that list of points by vertical
coordinate, and for each row sort again by horizontal component. Discard pairs
of duplicate points. The remaining points, taken in pairs, define the
horizontal line segments. (Since points are added four at a time, and
duplicates are discarded two at a time, there will always be an even number of
points.)
To get the vertical line segments, sort the endpoints of the horizontal line
segments, sorting first by horizontal coordinate and within each column by
vertical coordinate, and take the resulting list of points in pairs.
Caveat: the line segments produced delineate the XOR of the rectangles. That's
the same as UNION only if the rectangles do not overlap. That's why we needed
to discard mirrored displays.
Interesting Generalization: You can turn an XOR into a UNION by XORing back the
INTERSECTION. That is: A∪B = A ⊗ B ⊗ (A∩B). If we had to worry about
overlapping but not identical rectangles, the first step would be:
1. Make an empty list of rectangles, L
2. For each display, let its bounding rectangle be A and set L to L ∪ { A ∩ B |
B ∈ L } ∪ {A}. (That is, add to L not only A but also the intersection of A
with each rectangle that was already in L before we reached this display. Empty
intersections do not need to be added.)
Proceed as before. Make a list of the corner points of the rectangles in L.
Discard duplicate points in pairs. Sort by y and within that by x and pull off
points in pairs to make the horizontal line segments. Sort by x and within that
by y and pull off points in pairs to make the vertical line segments.
Caveat: assigning a clockwise/counterclockwise orientation to the line segments
can't be done. If you have only two rectangles, and they touch only at a
corner, you'll get horizontal and vertical segments that cross at that corner,
without ending there. Each of those line segments will be partly clockwise and
partly counterclockwise. The ambitious student could resolve this by assigning
orientations to the points and, when deleting duplicate points, not delete a
NW/SE or NE/SW pair. Details are beyond the scope of this missive. (And
besides, the situation cannot arise with displays.)
-Ron Hunsinger
_______________________________________________
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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:
https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to arch...@mail-archive.com
