Skyline Algorithm – Divide and Conquer

Give a list of tuples – where each tuple has 3 value – (x1, x2, h1) – each tuple represents a rectangular block of a building in the city skyline.

x1 – Start Coordinate of a Block on X Axis
x2 – End Coordinate of a Block on X Axis
h1 – Height of the block

Once a list of such tuples is given he problem is to find out the general skyline of the City int he 2D plane – where 1 building’s coordinates could be overlapping with another building and changing the skyline from a 2D perspective

For Example if we have a set of tuples as below

(1,5,10)
(2,7,9)
(4,15,12)
(6,9,15)

The general skyline algorithm should return

(1,4,10), (4,6,12), (6,9,15), (9,15,12)

Algorithm
I use a recursive Divide and Conquer Algorithm where I break up the original list into a list of smaller tuples.
When there is only 1 or 2 tuple in a list – we call the merge() routine to merge 2 tuples.

The results are printed as a set of blocks using matplotlib graphing library

Code

https://github.com/palsumitpal/sumitpython/blob/master/SkylineNew.py

Command Line
python SkyLineNew.py 1 4 10 4 6 12 6 9 15 9 15 12

// where you have a set of 3 numbers – which represents a tuple and
// have any number of such tuples

// the program exits if any number is a -ve number and if the
// number of entries is not a multiple of 3

The code finally generates a graph of the Skyline using matplotlib python library – something like the one below

SkyLine

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s