Skyline Algorithm

Hey,

I'm sure most coders are aware of the Skyline Problem, I'm working on coding it right now, but I'm stuck (hence why would I be asking this question ). Anyway, My problem isn't scanning the numbers within the file or anything, it's producing the output numbers by judging which triples precede, overlap and then end, thus creating a new section of the skyline.

For example:


I've got image 1 (left side) triples, I'm trying to create image 2 (left side) by the data. Any ideas?

Its a matter of comparing adjacent triples. If the horizontal magnitude of a following triple is less than that of the preceding triple's greatest horizontal magnitude and the vertical magnitude of the leading triple is greater, the following point is obscured, i.e. disappears. There are only a small number of possibilities to compare and dispose of.

hi
I'am a student doing my Masters In an American University

can u pls forward or post any C++ program on skyline problem
here in the forum

I could not find any sample program in the web


Thank you

I'm not sure exactly what DaWei_M was saying (we may never know ), but I'd do this with a simple sweep algorithm: imagine a vertical line sweeping over the entire plane, moving from left to right. At any given x-coordinate, it intersects the top edges of the rectangles at a finite set of heights. This data only changes at a finite number of events: when the x-coordinate of the sweep line crosses either the beginning or the end of one of the rectangles, which corresponds respectively to adding or removing a intersection with the sweep line. At the top level of the algorithm, you need to figure out what all these events are in sequence (just sort all the x-coordinates), and for processing the events, it's just a matter of finding the right data structure so that you can efficiently add and remove heights and find the top one to output.