CS 232
Algorithms and Data Structures
Skyline Assignment


Background

    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.

Helper classes

   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.

Phase I (due Friday, February 7, at 4 p.m.)

It is always better to determine your test data before you begin writing code.  Doing so prevents you from designing your test data to cover only those cases you dealt with in the code.  Therefore, the first phase of the assignment requires that you create a test suite against which you will run your code.  Your test suite should be presented as a JUnit test suite.  Each test method in your suite should be public, void, parameterless, and start with the letters "test" followed by your initials and then the string "2014".  You should assume that you are testing a Skyline class which has a method with the following signature:

     public static List<Point> makeSkyline(List<Building>)

To help you with the testing, a buggy Skyline class is provided in the file Buggy.jar.  The makeSkyline method in this class works unless the input List has size 3.  A probably working version of the class is found in Hopeful.jar.

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. 

Phase II (due Friday, February 7, at 4 p.m.)

The assignment for Phase II is to demonstrate that you can use both of these classes effectively.  You are therefore to write a program that builds a List of Buildings and a List of Points and displays them using a SkylineViewer object.  The List of Points can be "hard-coded"; in this phase you are not required to compute the skyline.  (Note: The classes are part of a package named CS232.  Be sure to treat them properly in your project.) 

Phase III (due Wednesday, March 12 at 4 p.m.)

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.

Phase IV (due Wednesday, March 12 at 4 p.m.)

In this phase, the format of the input and output is the same as in Phase III, but it is possible that some buildings overlap.  The skyline is to be computed by an insertion-sort-like algorithm where each building is added to the skyline of the buildings that preceded it.  This will result in a running time that is quadratic in the length of the input.

Phase V (due Wednesday, March 12at 4 p.m.)

The input and output for this phase is identical to that of Phase IV, but this time, you must use a divide-and-conquer, merge-sort-like algorithm.  This will result in an O(N*logN) algorithm.  If Phase IV has been coded correctly, the code to merge one building into an existing skyline can easily be modified to merge two existing skylines into one.  This should make Phase V considerably easier than Phase IV.