Re: Desktop geometry problem
Re: Desktop geometry problem
- Subject: Re: Desktop geometry problem
- From: Ron Hunsinger <email@hidden>
- Date: Mon, 11 Jun 2012 14:08:36 -0700
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 (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