Title: Solve the skyline problem in C#

In the "skyline problem" you are given a collection of rectangles all with a common baseline and the goal is to find an enveloping silhouette. The result looks like like the skyline for a city with a bunch of sky scrapers.

When you enter a number in the example's text box and click Go, the program creates that number of random rectangles and then solves the skyline problem for them.

One way you might try to solve the problem I'll call "the painter's algorithm" (named after a graphics algorithms that has some similar characteristics). The idea behind that approach is to make an array representing the Y coordinates of the rectangles for various X coordinates. For example, you could use one entry per horizontal pixel. If you wanted to draw the scene 1000 pixels wide, you would make an array with 1000 entries.

Next you would loop through the rectangles and set the values of the array for the pixels with that rectangle's X coordinates to be the maximum of their current values or the rectangle's height.

That method works and is reasonably straightforward but it's somewhat unsatisfying because it depends on the resolution of the drawing. It also may require you to allocate a fairly large array even if you only have a few rectangles.

Here's another algorithm that doesn't have those drawbacks.

1. For each rectangle, create two "event" objects,one representing the rectangle's starting X coordinate and one representing its ending X coordinate.
2. Sort the events by their X coordinates.
3. Initialize a current_height variable to 0.
4. Loop through the events. For each event:
   1. If the event is the start of a rectangle:
      1. Add the rectangle to an active list.
      2. If current_height < the rectangle's height, set current_height = the rectangle's height.
   2. If the event is the end of a rectangle:
      1. Remove the rectangle from the active list.
      2. Set current_height = the height of the tallest rectangle still in the active list.

The example program uses the following BuildingEvent class to represent the start or end of a rectangle.

public class BuildingEvent : IComparable<BuildingEvent> { public enum EventTypes { Start, End }; public int X; public EventTypes EventType; public int BuildingIndex; public BuildingEvent(int x, EventTypes event_type, int building_index) { X = x; EventType = event_type; BuildingIndex = building_index; } public int CompareTo(BuildingEvent other) { return X.CompareTo(other.X); } }

The class implements IComparable so it is easy to sort an array of BuildingEvent objects.

A BuildingEvent object has properties to record an event's X coordinate, the event type (Start or End), and the index of its rectangle.

The following FindSkyline method uses the BuildingEvent class to find the skyline polygon.

// Return a skyline point list for the rectangles. private List<Point> FindSkyline(Rectangle[] buildings) { // Create building start and end events. int num_buildings = buildings.Length; List<BuildingEvent> building_events = new List<BuildingEvent>(); for (int i = 0; i < num_buildings; i++) { building_events.Add(new BuildingEvent( buildings[i].X, BuildingEvent.EventTypes.Start, i)); building_events.Add(new BuildingEvent( buildings[i].Right, BuildingEvent.EventTypes.End, i)); } // Sort the events. building_events.Sort(); // Make a list for the currently active buildings. List<Rectangle> active_buildings = new List<Rectangle>(); // Initially ymin is the building baseline. int ground = buildings[0].Bottom; int ymin = ground; // Make the result list. List<Point> results = new List<Point>(); results.Add(new Point(0, ymin)); // Process the events. int num_events = 2 * num_buildings; foreach (BuildingEvent building_event in building_events) { // Get the building index; int building_index = building_event.BuildingIndex; // Get the event's X coordinate. int event_x = building_event.X; // See if it's a start or stop. if (building_event.EventType == BuildingEvent.EventTypes.Start) { // It's a start. // See if this building is taller // than the currently active one. if (buildings[building_index].Top < ymin) { results.Add(new Point(event_x, ymin)); ymin = buildings[building_index].Y; results.Add(new Point(event_x, ymin)); } // Add the building to the active list. active_buildings.Add(buildings[building_index]); } else { // It's a stop. // Remove the building from the active list. active_buildings.Remove(buildings[building_index]); // See if this building was the tallest. if (buildings[building_index].Top <= ymin) { // This building was tallest. // Mark this point. results.Add(new Point(event_x, ymin)); // Find the new tallest active building. if (active_buildings.Count == 0) ymin = ground; else { ymin = active_buildings[0].Top; for (int j = 1; j < active_buildings.Count; j++) { if (ymin > active_buildings[j].Top) ymin = active_buildings[j].Top; } } // Mark this point. results.Add(new Point(event_x, ymin)); } } } // Add a final point off to the right. results.Add(new Point(10000, ground)); return results; }

This code follows the algorithm in a reasonably straightforward manner but I want to mention a couple of things.

First, notice how easily the code sorts the array of events. Because the BuildingEvent class implements IComparable, the method can simply call the list's Sort method to sort it.

Second, this code uses a simple list to keep track of the active rectangles. When it needs to find the tallest currently active rectangle, the code searches through this list. If the list is large, that can be inefficient. If the list contains O(N) of the rectangles at once, then searching it O(N) times will take O(N²) steps.

A more efficient approach would be to store the active rectangles in a priority queue such as a heap. Then finding the tallest rectangle and updating the heap will require only O(log N) steps so doing that N times will take a total of only O(N log N) steps.

For small example such a this one, the difference in speed is insignificant and the code would be much more complicated so I'm not including a heap in this example. Feel free to download the example and modify it if you like.

Download the example to experiment with it and to see additional details.