The Skyline Problem

Background:

With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas (CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines (lines obscured by other parts of a drawing).

 

The Problem:

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple (Li, Hi, Ri) where Li and Ri are left and right coordinates, respectively, of building i and Hi is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28). The skyline on the right, is represented by the sequence: (1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)

The Input:

The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by Li, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

 

The Output:

The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector (v1,v2,v3,…, vn-2,vn-1,vn), the vi is such that if i is an even number then it represents a horizontal line (height). If i is an odd number then it represents a vertical line (x-coordinate). The skyline vector should represent the path taken, for example, by a bug starting at the minimum x-coordinate and travelling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

using System.IO;

using System.Text.RegularExpressions;

 

namespace Skyline

{

    class Skyline

    {

        static void Main(string[] args)

        {

            try

            {

                //Reading the building triples from a file C:\skyline.txt

                StreamReader sr = new StreamReader(@"C:\skyline.txt");

                ArrayList inputVector = new ArrayList();

                Console.WriteLine("Sample Input:");

                Console.WriteLine("=============");

                for (string str = sr.ReadLine(); str != null; str = sr.ReadLine())

                {

                    inputVector.Add(str);

                    Console.WriteLine(str);

                }

                sr.Close();

                int[,] matrix = new int[inputVector.Count,3];

                Regex reg = new Regex(" ");

                int maxValue = 0;

                //Parsing the input vector and retrieving the coordinates in matrix

                for (int i = 0; i < inputVector.Count; i++)

                {

                    int column = 0;

                    foreach (string val in reg.Split(inputVector[i].ToString()))

                    {

                        matrix[i, column] = int.Parse(val);

                        column++;

                        //check for max value

                        if (column == 3 && maxValue < matrix[i,column-1])

                        {

                            maxValue = matrix[i, column – 1];

                        }

                    }

                }

                int[] linearArray = new int[maxValue + 1];

                //Initializing the linear array to 0

                for (int i = 0; i <= maxValue; i++)

                {

                   linearArray[i] = 0;

                }

                for (int i = 0; i < inputVector.Count; i++)

                {

                    for (int j = matrix[i, 0]; j < matrix[i, 2]; j++)

                    {

                        if (linearArray[j] < matrix[i, 1])

                        {

                            linearArray[j] = matrix[i, 1];

                        }

                    }

                }

                Console.WriteLine("Sample Output:");

                Console.WriteLine("==============");

                for (int i = matrix[0, 0]; i <= maxValue; i++)

                {

                    if (linearArray[i] != linearArray[i – 1])

                    {

                        Console.Write(i + " " + linearArray[i] + " ");

                    }

                }

                Console.WriteLine();

            }

            catch (Exception e)

            {

                Console.WriteLine(e.Message);

            }

        }

    }

}

 

Sample Input:

=============

1 11 5

2 6 7

3 13 9

12 7 16

14 3 25

19 18 22

23 13 29

24 4 28

Sample Output:

==============

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

Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

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