This programming project will require you to implement (in Java) a pair of algorithms to determine the two-dimensional skyline of a set of buildings. The assignment comes in five phases. The first phase is due Monday, January 24, at the beginning of class. For this phase, and this phase ONLY, you may work in groups of up to three. All other phases are due Wednesday, March 23 and must be completed on your own, as an Individual Project with No Collaboration, as outlined in the department's Academic Practices and Policies document. As you are maturing programmers, your assignment will be graded on correctness and documentation, but also structure and style. You are encouraged to discuss programming details with the instructor.
For each phase, it will be expected that the program has incorporated all relevant portions of the previous phases. Any errors found in one phase and not subsequently corrected, will result in a deduction in subsequent phases as well. If two or more phases are submitted simultaneously, then it is possible that a single error could result in multiple deductions. The instructor promises to return each phase to the student within one week (spring break not included) of its receipt. Should he fail to do so, an extension will be granted to any student so affected. If the phases are submitted too late, however, it is possible that feedback will not be available in a timely fashion. It is the student's responsibility to plan around this.
The Problem
We imagine a city situated on a plain, with all of its buildings aligned to the coordinate axes and all of the building are rectangular prisms. The input to the problem is a list of buildings, each specified by its left x-coordinate, its top y-coordinate, and its right y-coordinate in that order. The output is an ArrayList of Points, describing the outline of the skyline. Two examples are shown below:
In this case, the buildings are (20,40,90), (100,150,120), (150,5,190), and the skyline is (20,40), (90,0), (100,150), (120,0), (150,5), (190,0).
In this case, the buildings are (40,60,90), (70,150,130), and the skyline is (40,60), (70,150), (130,0). Note that the picture does not show the overlap of the buildings in any particular manner.
The skyline proceeds from one point of the skyline to the next by moving horizontally (at the current y-value) until the x-value of the next Point is reached. It then proceeds vertically until the y-value of that Point is reached. It continues to do so until all of the Points have been accounted for. The x-values in a skyline are strictly increasing.
Note that consecutive Points in the skyline should NOT have equal x- or y-values. Such points indicate the presence of an extraneous Point that is not needed. All skylines are assumed to start at (0,0), and the y-value of the last Point of all skylines should be 0 as well.
The format of the input is a line with a single integer (N) representing the number of buildings in the skyline. This is followed by N lines of three integers each, representing the left, top, and right values of each of the N buildings. You may assume that all of the input is in the correct format.
The output is two-fold. You are to display a skyline viewer with both the buildings and the skyline drawn. You are also to print two lines of output on the console. The first is the String "Buildings: ", followed by an ArrayList containing the buildings (in the order they were entered by the user.) The second is the String "Skyline: ", followed by the ArrayList containing the Points of the skyline. In both cases exactly two spaces follow the colon.