Desktop geometry problem

  • Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:

    1. It should be the actual perimeter of the desktop, not just the bounding box.
    2. It should be a single polygon, rather than a collection of rectangles.
    3. It should behave properly in the presence of mirrored displays.

    I do not care about aberrant or hypothetical scenarios such as a desktop that's disjoint or has holes in it.

    Thanks in advance for any pointers.
  • On 07/06/2012, at 9:23 PM, Gregory Weston wrote:

    > Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:
    >
    > 1. It should be the actual perimeter of the desktop, not just the bounding box.
    > 2. It should be a single polygon, rather than a collection of rectangles.
    > 3. It should behave properly in the presence of mirrored displays.

    Just iterate over the list of NSScreens and append each screen rect to a bezier path.

    --Graham
  • On Jun 07, 2012, at 10:22 PM, Graham Cox <graham.cox...> wrote:

    On 07/06/2012, at 9:23 PM, Gregory Weston wrote:

    > Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:
    >
    > 1. It should be the actual perimeter of the desktop, not just the bounding box.
    > 2. It should be a single polygon, rather than a collection of rectangles.
    > 3. It should behave properly in the presence of mirrored displays.

    Just iterate over the list of NSScreens and append each screen rect to a bezier path.
     
    First thing I tried. It fails requirement #2.
  • On 08/06/2012, at 12:30 PM, gweston wrote:

    > On Jun 07, 2012, at 10:22 PM, Graham Cox <graham.cox...> wrote:
    >
    >>
    >> On 07/06/2012, at 9:23 PM, Gregory Weston wrote:
    >>
    >>> Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:
    >>>
    >>> 1. It should be the actual perimeter of the desktop, not just the bounding box.
    >>> 2. It should be a single polygon, rather than a collection of rectangles.
    >>> 3. It should behave properly in the presence of mirrored displays.
    >>
    >>
    >> Just iterate over the list of NSScreens and append each screen rect to a bezier path.
    >
    > First thing I tried. It fails requirement #2.

    OK, so you'll need to get smart, and determine where the edges connect. With a few simple rectangles, calculating this union is a very easy problem, unlike, say, the general case of a union of arbitrary vector paths. But that can be solved, so this case is a very degenerate subset of that problem, since you know there is no overlap, nor any gaps.

    I don't believe there is a built-in solution for union (or other set ops) on bezier paths, much as I'd love there to be, and have had in as a bug report for a requested feature since about 2004. The old MacOS could do this with regions (though that was a bitmap operation, so definitely simpler), but OS X has never had a public API, even though one must exist internally to calculate clipping paths and so on.

    --Graham
  • On Jun 7, 2012, at 7:30 PM, gweston <gweston...> wrote:

    > On Jun 07, 2012, at 10:22 PM, Graham Cox <graham.cox...> wrote:
    >
    >
    > On 07/06/2012, at 9:23 PM, Gregory Weston wrote:
    >
    >> Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:
    >> 1. It should be the actual perimeter of the desktop, not just the bounding box.
    >> 2. It should be a single polygon, rather than a collection of rectangles.
    >> 3. It should behave properly in the presence of mirrored displays.
    >
    >
    > Just iterate over the list of NSScreens and append each screen rect to a bezier path.
    >
    > First thing I tried. It fails requirement #2.

    Is Requirement 2 really a requirement? What are you going to be doing with an NSBezierPath path that is going to be improved by making it a single polygon rather than a union of rectangles?

    --Kyle Sluder
  • On Jun 8, 2012, at 02:20, Kyle Sluder wrote:

    > On Jun 7, 2012, at 7:30 PM, gweston <gweston...> wrote:
    >
    >> On Jun 07, 2012, at 10:22 PM, Graham Cox <graham.cox...> wrote:
    >>
    >>
    >> On 07/06/2012, at 9:23 PM, Gregory Weston wrote:
    >>
    >>> Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:
    >>> 1. It should be the actual perimeter of the desktop, not just the bounding box.
    >>> 2. It should be a single polygon, rather than a collection of rectangles.
    >>> 3. It should behave properly in the presence of mirrored displays.
    >>
    >>
    >> Just iterate over the list of NSScreens and append each screen rect to a bezier path.
    >>
    >> First thing I tried. It fails requirement #2.
    >
    > Is Requirement 2 really a requirement? What are you going to be doing with an NSBezierPath path that is going to be improved by making it a single polygon rather than a union of rectangles?

    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.
  • On Jun 8, 2012, at 4:01 AM, Gregory Weston <gweston...> 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.

    Perhaps I should ask more directly: what is your end goal? What are you going to do with these line segments once you have them? Are there alternative approaches to your goal that don't rely on doing a shape union?

    --Kyle Sluder
  • Searching "bezier path simplify" turned up some interesting results, like this from cocoadev: http://cocoadev.com/wiki/NSBezierPathcombinatorics

    Since you have no curves this may be overkill, but I'm sure there's an algorithm out there somewhere for non-intersecting rectangles.

    ----- Original Message -----
    From: "Gregory Weston" <gweston...>
    To: "Kyle Sluder" <kyle...>
    Cc: <cocoa-dev...>
    Sent: Friday, June 8, 2012 4:01:03 AM
    Subject: Re: Desktop geometry problem

    On Jun 8, 2012, at 02:20, Kyle Sluder wrote:

    > On Jun 7, 2012, at 7:30 PM, gweston <gweston...> wrote:
    >
    >> On Jun 07, 2012, at 10:22 PM, Graham Cox <graham.cox...> wrote:
    >>
    >>
    >> On 07/06/2012, at 9:23 PM, Gregory Weston wrote:
    >>
    >>> Does anyone know of existing code or a trivial technique to get a CGPath or NSBezierPath that describes the shape of the desktop? I'll write and share it if it's not out there, but I'd rather not reinvent any wheels. My interests are:
    >>> 1. It should be the actual perimeter of the desktop, not just the bounding box.
    >>> 2. It should be a single polygon, rather than a collection of rectangles.
    >>> 3. It should behave properly in the presence of mirrored displays.
    >>
    >>
    >> Just iterate over the list of NSScreens and append each screen rect to a bezier path.
    >>
    >> First thing I tried. It fails requirement #2.
    >
    > Is Requirement 2 really a requirement? What are you going to be doing with an NSBezierPath path that is going to be improved by making it a single polygon rather than a union of rectangles?

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

    Yes it can. It's not particularly useful, but I've done it when testing coordinate calculations.
previous month june 2012 next month
MTWTFSS
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
Go to today