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

### Like this:

Like Loading...

*Related*