Draw skyline algorithm test data valid output?

#1

Hi,
I have a question on the skyline draw test data. The first one here:
buildings: [[378, 441, 28], [151, 286, 87], [763, 949, 39], [968, 1066, 54], [431, 494, 1], [468, 540, 24], [859, 988, 95], [909, 950, 89], [670, 769, 96], [708, 728, 24], [176, 254, 60], [773, 820, 33], [66, 239, 96], [768, 961, 10], [13, 30, 84], [675, 744, 30], [652, 833, 36], [321, 489, 51], [722, 814, 79], [800, 806, 64], [390, 516, 55], [884, 884, 56]]
expected: [[13, 30, 84], [31, 65, 0], [66, 239, 96], [240, 286, 87], [287, 320, 0], [321, 389, 51], [390, 516, 55], [517, 540, 24], [541, 651, 0], [652, 669, 36], [670, 769, 96], [770, 814, 79], [815, 858, 39], [859, 988, 95], [989, 1066, 54]]

Look at the merge skyline between 66 to 286 here. The buildings involved are:
[66, 239, 96], [151, 286, 87], I think the merge should be [66, 239, 96], [239, 286, 87] but expected data here seem to break the line here. [66, 239, 96], [240, 286, 87]. Also when there are empty space with no buildings from 30 to 66 and 540 to 652, test data seem to use left+1, right-1 to fill up the empty space and I think merge should be [30,66,0] and [540,652,0]

I used line sweep algorithm to calculate skyline contour but got different merge result. The major differences are as described above.
My result is
result: [[13, 30, 84], [30, 66, 0], [66, 239, 96], [239, 286, 87], [286, 321, 0], [321, 390, 51], [390, 516, 55], [516, 540, 24], [540, 652, 0], [652, 670, 36], [670, 769, 96], [769, 814, 79], [814, 859, 39], [859, 988, 95], [988, 1066, 54]]

My question is : is the output triplet data(<left, right, height>) needed to be all none-overlapping?

Thank you

0 Likes

#2

The data format is like left and right closed interval. That is the reason you see no-overlapping of the result. IF you change your definition of interval to left and right close, you will get the answer like we have.

0 Likes