The Skyline Problem

I have been working on this problem for a few days, and have accumulated 3 different approaches, nearly a dozen tests and a few hundred lines of code.

(This article by Brian Gordon is a good one if you don't know what the skyline problem is.)

My first two approaches were different formulations of creating a list of rectangles that did not have any overlapping bits.

This was complicated by the fact that I could not and still can't write a function that works something along the lines of:

function :: [Rectangle] -> [Rectangle]

function = foldl helper []

In this case, the helper function is meant to consume the original list of rectangles one at a time and produce a list of rectangles that don't have any overlap. It traverses the list only once, and from that you can do a mapping to produce either the area under the line or the list of points required to draw the skyline.

My most successful attempt requires transforming each Rectangle into a list of tuples:

xheight :: Rectangle -> [(Int,Int)]

xheight (Rectangle left right top) = map (,top) [left .. (right - 1)]

And then taking the maximum at each x-coordinate.

I still have a couple of edge cases that I need to work through to make it work perfectly -- unless I further down the rabbit hole than I currently think I am -- but I am getting closer.

This is pretty much my learning process, punctuated by moments of hey, it passed all my tests, and followed by oh wait, that doesn't actually work.

PS If you are interested to see what I have done so far: May's Github -- see files skyline, nonoverlap and xRect.