CSc 301 Programming Problem


One of the problems that occurs in computer graphics 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 (L,H,R ) where L and R are left and right coordinates, respectively, of a building and H is the height of the building. In the diagram below buildings are shown for these triples : 
B= (1; 11; 5); A= (2; 6; 7); C= (3; 13; 9); D= (12; 7; 16); E= (14; 3; 25); 
F= (19; 18; 22); H= (23; 13; 29); G= (24; 4; 28) 


8                   ffff
7                   ffff
6                   ffff
5                   ffff
4                   ffff  
3    cccccc         ffffhhhhhhh
2    cccccc         ffffhhhhhhh
1 bbbbbcccc         ffffhhhhhhh
0 bbbbbcccc         ffffhhhhhhh
9 bbbbbcccc         ffffhhhhhhh
8 bbbbbcccc         ffffhhhhhhh
7 bbbbbcccc  ddddd  ffffhhhhhhh
6 baaaaaacc  ddddd  ffffhhhhhhh
5 baaaaaacc  ddddd  ffffhhhhhhh
4 baaaaaacc  ddddd  ffffhgggggh
3 baaaaaacc  ddeeeeeeeeeeeegggh
2 baaaaaacc  ddeeeeeeeeeeeegggh
1 baaaaaacc  ddeeeeeeeeeeeegggh
 012345678901234567890123456789
           1         2
In the diagram above, building A is in front of B which is in front of C. Building E is in front of D, F, G, & H. G is in front of H.

The Input
The input is a sequence of building triples. All coordinates of buildings are integers less than 10,000, as is the height. There will be at least one building in the input. All integers are separated by one or more spaces or newlines. The triples will be sorted by L , the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input. L >= 0 and R >= L.

The Output
The output should consist of an array that describes the skyline as shown in the example above. In the skyline array { H0, H1, H2, H3, H4, ... H9999} Hi is a number that represents the height of the skyline at position i. The output array has 10,000 elements..

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

0,11,11,11,13,13,13,13,13,13,0,0,7,7,7,7,7,3,3,18,18,18,18,13,13,13,13,13,13,13,0,....


Implementation


You must follow this Java class definition: 
public class Skyline
{
    /** Compute the skyline for a group of buildings.
     * @param rdr a reader that contains the input sequence of building triples.
     * @return an array of integers describing the skyline.
     */    
    public int[] compute(java.io.Reader rdr)
Example invocation: 
        Skyline sky = new Skyline();	
        String set1 = "2 2 2\n3 3 3\n";
        StringReader sr = new StringReader(set1);
        int[] result = sky.compute(sr);
Note: Please design your own solution. While this algorithm is easy to find on the Web or in textbooks, please write your own algorithm from scratch.   There are many approaches to the solution with a wide range of difficulty.  You might consider several alternative designs before committing to one solution.

Unit Testing

You must submit execution output that demonstrates that your program can produce the correct results for data in the Example above.  This output can be created in one of two ways:

Perform any additional tests you want to convince yourself that your solution is correct.

Acceptance Testing

In addition, your program must pass the instructor's acceptance test.  Once you are satisfied that your program is correct and is passing your unit tests, create a new time log entry.  Enter "Test" for the phase and in the comment field enter "Acceptance Testing".

Submit your source code using the Web-CAT grader. On this project the grader will not run your own unit tests. Web-CAT will report checkstyle errors in red and they WILL count in your total score. Each coding standard violation is a defect. The defect type is 10 for code syntax, and 80 for Javadoc errors. (Tip: To avoid getting style errors in Web-CAT, run the Checkstyle extension in BlueJ before submitting to Web-CAT.)

If Web-CAT reports any errors, tally them in a new section of the defect tally with a removal phase of "Acceptance Testing".  You are allowed five Web-CAT submissions without penalty.  If you take more than five submissions, your project earns only half-credit.

When Web-CAT assigns a 100% score to your work, you should finalize your work according to the assignment directions.