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, 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)