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 two phases are due Friday, February 7, at 4 p.m.. All other phases are due Wednesday, March 12 at 4 p.m. 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 three class days (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 List 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); this point is not included in the skyline. The y-value of the last Point of all skylines should be 0 as well.
Two classes, Building and SkylineViewer, are provided for you. The Building class is a simple encapsulation (similar to the Point class, but with no public data) that holds the input values. The SkylineViewer class will permit you to examine your input and output in a graphical context. These will are provided in the file SkyLineHelper.jar. Documentation for these classes is also provided.
The Corona project, designed by Steve Andrianoff, Coty Collins, Dan Eisemann, and David Levine, should aid you considerably in your completion of this phase. A brief "lab write-up" that mostly matches the demo in class is available to help you with the logistics of creating your JUnit tests.
You are to create a class named Skyline with that includes (at least) the makeSkyline method described above. For this phase only, you may assume that the buildings are disjoint - in fact that there is an alley between all buildings.