### The Skyline Problem

### Lab3.2 The Skyline Problem

The skyline problem is defined as given n rectangular buildings in a 2-dimensional city, compute the skyline of these buildings, eliminating hidden lines. The main task is to view buildings from a side and remove all sections that are not visible. All buildings share common bottom and every building can be represented by triplet (Left, Height, Right)

As an example, if the buildings array is

[[1, 11], [3, 13], [9, 0], [12, 7], [16, 3], [19, 18], [22, 3], [23, 13], [29, 0]]

As an example, if the buildings array is

[ [1, 11, 5], [2, 6, 7], [3, 13, 9], [12, 7, 16], [14, 3, 25], [19, 18, 22], [23, 13, 29], [24, 4, 28] ]then the skyline is

[[1, 11], [3, 13], [9, 0], [12, 7], [16, 3], [19, 18], [22, 3], [23, 13], [29, 0]]

buildings = [ [1, 11, 5], [2, 6, 7], [3, 13, 9], [12, 7, 16], [14, 3, 25], [19, 18, 22], [23, 13, 29], [24, 4, 28] ] def getSkyLine(B): return list(([B[0], B[1]], [B[2], 0])) def setSkyLine(B1, B2): # B1 = Sky line of building 1 & B2 = Sky line of building 2 h1 = 0; h2 = 0 # Height of buildings from B1 & B2 # Skyline to return SkyLine = [] # Indexes to iterate through each building set B1_i = 0; B2_i = 0; while ((len(B1) > B1_i) and (len(B2) > B2_i)): # Compare x position of each building if (B1[B1_i][0] <= B2[B2_i][0]): # h1 gets the first strip height h1 = B1[B1_i][1] # Add the current maximum height as the # height of the current strip if h1 >= h2: newHeight = h1 else: newHeight = h2 # Create the new strip of the skyline and # add it to the skylines building up if not ((len(SkyLine) != 0) and (SkyLine[len(SkyLine) - 1][1] == newHeight)): SkyLine.append([B1[B1_i][0], newHeight]) # Increment the index to move to the next # building strip B1_i = B1_i + 1 else: # h2 gets the first strip height h2 = B2[B2_i][1] # Add the current maximum height as the # height of the current strip if h1 >= h2: newHeight = h1 else: newHeight = h2 # Create the new strip of the skyline and # add it to the skylines building up if not ((len(SkyLine) != 0) and (SkyLine[len(SkyLine) - 1][1] == newHeight)): SkyLine.append([B2[B2_i][0], newHeight]) # Increment the index to move to the next # building strip B2_i = B2_i + 1 # If there are elements left in B1 or B2, that means # they are higher strips while (B1_i < len(B1)): # h1 gets the first strip height h1 = B1[B1_i][1] # Add the current maximum height as the # height of the current strip if h1 >= h2: newHeight = h1 else: newHeight = h2 # Add it to the skylines building up if not ((len(SkyLine) != 0) and (SkyLine[len(SkyLine) - 1][1] == newHeight)): SkyLine.append([B1[B1_i][0], newHeight]) B1_i = B1_i + 1 while (B2_i < len(B2)): # h2 gets the first strip height h2 = B2[B2_i][1] # Add the current maximum height as the # height of the current strip if h1 >= h2: newHeight = h1 else: newHeight = h2 # Add it to the skylines building up if not ((len(SkyLine) != 0) and (SkyLine[len(SkyLine) - 1][1] == newHeight)): SkyLine.append([B2[B2_i][0], newHeight]) B2_i = B2_i + 1 # Return the skyline calculated return SkyLine def FindSkyLine(B): # Calculate length of B length = len(B) # If there's only one building, if (length == 1): return getSkyLine(B[0]) else: # Find the mid point to break the set of buildings mid_value = length / 2 # Find skyline of both set B1 = FindSkyLine(B[:mid_value]); B2 = FindSkyLine(B[mid_value:]); return setSkyLine(B1, B2) print FindSkyLine(buildings)

## Comments

## Post a Comment