skyline algorithm

Question

How do I find the vertices of the broken line that surrounds the silhouette in this image?

A possible input for the example above is:

WIDTH  HEIGHT  POSITION
  3       9       17
  5       9        9
 12       4        8
  3      11        3
 10       7        1
  2       3       19

So for this example the solution would be

[(1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), 
 (9, 7), (9, 9), (14, 9), (14, 4), (17, 4), (17, 9), 
 (20, 9), (20, 3), (21, 3), (21, 0)]

Answer 1

In the naive case, this doesn't seem like a very difficult algorithm. Do you know if the input size will get large/how large?

My initial attempt: Try to move from left to right. First pick the block with the leftmost edge that exists on the origin line. Climb to its top. Find all blocks with a left edge between the current point and the upper right point of the current block. Of that set, pick the closest (but check for edge cases, pun not intended). If the set is empty, start working your way down the right side of the block, looking for other blocks you may intercept.

Basically this is just how you'd trace it with your eye.

You can do some simple optimization by keeping sorted lists and then searching the lists rather than finding sets and digging around. For example, you might keep 4 sorted lists of the blocks, each sorted by the x or y coordinate of one of the sides.

If you have many, many blocks, you could consider using a multi-dimensional data structure to further organize the information.

Answer 2

http://online-judge.uva.es/p/v1/105.html is where I originally saw the problem

And Algorithmist has an explanation of the solution: http://www.algorithmist.com/index.php/UVa_105

Answer 3

This is pretty simple. Make an array that is the length of the X axis, initialize to 0. As you read in the inputs, write the heights into this array if the height is >= the current value at that location in the array.

Then just loop over the array, and every time the value changes it is a vertex.

Basically:

int heights[SIZE] = {0};
int i, width, pos, height, prev = -1;
while (scanf("%d %d %d", &width, &height, &pos) == 3) {
    for (i = 0; i < width; ++i) {
        if (heights[pos+i] < height)
            heights[pos+i] = height;
    }
}

for (i = 0; i < SIZE; ++i) {
    if (heights[i] != prev) {
        printf("(%d,%d) ", i+1, heights[i]);
        prev = heights[i];
    }
}
printf("\n");