c - 天际线算法

Question

如何找到这张图片中轮廓周围虚线的顶点？

上述示例的可能输入是:

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

所以对于这个例子，解决方案是

[(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

这很简单。创建一个 X 轴长度的数组，初始化为 0。当您读入输入时，如果高度 >= 数组中该位置的当前值，则将高度写入此数组。

然后就循环遍历数组，每次值变化都是一个顶点。

基本上:

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");