Description

• This is an individual assignment. Please do not collaborate
• If you think that this document does not clearly describes the assignment, ask questions before its too late. This is a _Java Programming assignment. You will write a _Java program which solves a problem known as _The

Skyline Problem.

• Your program reads a file: txt
• According to content in _txt, the program utilizes necessary classes and solves the problem described below.
• Your program prints the solution to the standard output and at the same time creates a simple graphics window for the result.

The Skyline Problem

From a distance, the view of a collection of high-rise buildings reveals a profile. With sufficient simplifications, this observation turns into a problem called the skyline problem. The objective is to find the profile created by the roofs of the buildings. The simplifications are: All of the buildings are represented by rectangles and the profile is on 2D plane.

width height position

3 11 3

10 7 1 5 9 9

12 4 8

3 9 17 2 3 19

(21, 3)

Figure 1: Visualization

data.txt

• This file holds information about rectangles. Each line is related with a rectangle.
• Fields are all integers
• Fields are separated with spaces
• Format:

<width> <height> <position>

<width> <height> <position>

<width> <height> <position> .

.

.

• Example:

3 9 17 5 9 9

12 4 8

3 11 3

10 7 1

2 3 19

Output

• List all the corners of the skyline in the standard output.
• Make sure it is ordered. (i.e. when followed, creates a path of the skyline) Example:

1 (1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), (9, 7), (9, 9), (14, 9), (14, 4), (17, 4), , (17, 9), (20, 9), (20, 3), (21, 3), (21, 0)

Graphics Window

• Show the _skyline in a simple graphics window.
• Create a _JPanel, _JFrame, other necessary components and draw lines between the points listed in the solution.
• Pay attention to the coordinate system origin.
• If necessary, scale the drawing. (A path spanning a couple of pixels cannot be visible)

Remarks

• There is no limit on the number of rectangles.
• Rectangles are _not
• The same rectangle can appear more than once in _txt.
• Assume there isnt any errors in _txt.
• Grade weight is twice as much as of a regular assignment. In fact, this is two assignments combined in one.
• _{The Skyline Problem} is a well known problem and you can find a lot of help if you search the internet. But, this does not mean that you can copy an existing code. Try to understand the algorithm and come up with your implementation.
• A script will compare your code not just against your classmates submissions but against other code collected from different web pages.
• Provide a file(_pdf) which includes your comments about the program you implemented. Discuss its efficiency and make comments about its time complexity.