Introduction to Programming (CPSC 124)
—Hobart & William Smith Colleges, Spring 2015
Project #5
Home | Syllabus | Calendar | Class Notes | Labs and Projects | General Notes

Due by 12:19 pm on Monday, April 27

2-D Overlays

A common task in computer graphics is to render overlapping shapes in a manner that suggests their transparency. For example, we might want to vary the shading of an area depending on the number of overlapping shapes that cover that area:

Your Job

To give you a sense of the work involved, you are to write a program that, given a set of shapes and their coordinates, determines how many shapes cover a given point.

Input will be read from a file in the following format: On the first line will be an integer 1 ≤n. Following this will be n lines, each one designating a shape. The possible shapes you must be able to read are a circle, an ellipse, a rectangle, and a square. The formats of each are the following:

circle x  y  rad
ellipse x1 x2 y a b
rectangle x y wid hgt
square x y wid

The first of these describes a circle of radius rad, with center point (x,y). An ellipse specification designates an ellipse with foci (x1,y) and (x2,y), with semimajor axis length a and semiminor axis length b (if the foci have different y values, you have to introduce trigonometry, so we're going to simplify this part). A rectangle is given in terms of its bottom left point (x,y), its width, wid, and its height, hgt. Finally, a square is specified by its bottom left point (x,y) and its width, wid.

The next line following the n shapes will be a positive integer, 1 ≤m≤20, followed by m lines, each one containing the (x,y) coordinates of a point.

The output of your program consist of one integer for each point given, indicating the number of shapes that overlay that point.

Sample input file

A file containing information about the shapes and points depicted above would contain the following:

circle 0.0 0.0 1.2
rectangle -1.0 -1.0 2.2 3.0
ellipse 1.0 2.6 0.67 1.75 0.8
square 0.9 0.3 0.5
0.0 0.0
2.0 -1.5
-1.1 0.2
-0.5 -0.5
1.0 0.45

Sample output result

Suppose we save the input above in a file named "overlays.dat. Your program should run with the command depicted and produce the output below:

John-Lasseter:hw4 jlasseter$ java Overlays < overlays.dat

(Alternately, you can just invoke "java Overlays" and paste the input contents in to the input. It does the same thing.)

Useful Code

The goal of this assignment is for you to gain experience in solving problems using the data abstraction afforded by inheritance. To avoid your wasting time on other things, here is the beginning of a driver class. The main() method is complete, as is all the code for reading the input and constructing the correct Shape subclass (look at the constructor calls in the see* methods to get clues on how to define the constructors).

On the other hand, countOverlays() is just a prototype, which returns 0 every time. You'll need to provide a correct implementation of this method, as well as the various Shape classes.

import java.util.Scanner;

public class Overlays {
    public static void main(String[] args) {
        Scanner inp = new Scanner(;
        try {
           int numShapes = inp.nextInt(); 
           inp.nextLine(); // flush line break
           Shape[] shapes = new Shape[numShapes];
           for (int i = 0; i < numShapes; i++) {
               String line = inp.nextLine();
               shapes[i] = parseShape(line);
           int numpts = inp.nextInt(); inp.nextLine();
           for (int i = 0; i < numpts; i++) {
               Scanner line = new Scanner(inp.nextLine());
               Point p = new Point(line.nextDouble(),line.nextDouble());
               // ******** You'll need to implement countOverlays ********
               //                                   **********************
        } catch (java.util.InputMismatchException e) {
            throw new Error("Overlays.main(): " + e);
    } // main
    private static int countOverlays(Shape[] shapes, Point p) {
        return 0;  // PROTOTYPE
    private static Shape parseShape(String s) {
        Scanner spec = new Scanner(s);
        String kind =;
        if (kind.equals("circle"))
            return seeCircle(spec);
        else if (kind.equals("ellipse"))
            return seeEllipse(spec);
        else if (kind.equals("rectangle"))
            return seeRect(spec);
        else if (kind.equals("square"))
            return seeSquare(spec);
            throw new Error("parseShape:  internal bug");
    private static Circle seeCircle(Scanner parts) {
        double x = parts.nextDouble();
        double y = parts.nextDouble();
        double r = parts.nextDouble();
        return new Circle(new Point(x,y), r);
    private static Ellipse seeEllipse(Scanner parts) {
        double x1 = parts.nextDouble();
        double x2 = parts.nextDouble();
        double y = parts.nextDouble();
        double a = parts.nextDouble();
        double b = parts.nextDouble();
        return new Ellipse(new Point(x1,y), new Point(x2,y),a,b);
    private static Rectangle seeRect(Scanner parts) {
        double x = parts.nextDouble();
        double y = parts.nextDouble();
        double w = parts.nextDouble();
        double h = parts.nextDouble();
        return new Rectangle(new Point(x,y),w,h);
    private static Square seeSquare(Scanner parts) {
        double x = parts.nextDouble();
        double y = parts.nextDouble();
        double w = parts.nextDouble();
        return new Square(new Point(x,y),w);


In summary, you will need to write code for the following tasks:


Turn in:

John Lasseter