All code for this assignment is available in the ps9_programs folder in the cs111 download directory on the CS fileserver.

How to turn in this Problem Set

Hardcopy Submission

1. The cover page;
2. The final version of RectStairs.java from Task 1;
3. Your object diagram from Task 2a;
4. The final versions of Rect3.java, Rect4.java, and Rect5.java from Task 2b;
5. Your object diagram from Task 2c;
6. The final version of MorphingPolygon.java from Task 3.
7. The final version of MyAnimation.java from (optional) Extra Credit Opportunity.

Softcopy Submission

• The RectStairs subfolder should contain your final version of RectStairs.java from Task 1;
• The Rect subfolder should include your final versions of Rect3.java, Rect4.java, and Rect5.java from Task 2b;
• The MorphingPolygon subfolder should contain your final version of MorphingPolygon.java.
• The MyAnimation subfolder should contain your final version of any sprite and animation classes you created (if you did the extra credit problem).

Task 1: Rectangular Stairs (Independent Problem)

Task 1 is an independent problem (which is effectively a mini take-home exam). You may not consult with anyone else about this problem. (If you have any questions, you may of course ask Lyn or Elena; but we cannot help you to solve the problem.)

In this problem, you are asked to use Java graphics and iteration to define a method that creates staircase patterns like those illustrated below.

n = 4, c1 = Color.magenta, c2 = Color.cyan

n = 6, c1 = Color.red, c2 = Color.green

n = 10, c1 = Color.black, c2 = Color.yellow

All of the above examples are drawn by the following method, which you will define in this problem:

public static void rectStairs (Graphics g, Rectangle r, int n, Color c1, Color c2)
Using graphics context g, draw an n by n staircase pattern in rectangle r using colors c1 and c2. The staircase should consist of n columns. Assume the columns are indexed by i, which ranges from 1 to n. Then the ith column consists of (n + 1 - i) bricks that rest on the "ground", where each brick has a width that is 1/n the width of r and a height that is 1/n the height of r. Each brick in column i has painted on it a design that consists of i concentric rectangles whose colors alternate between c1 and c2. The outermost color in the design on the topmost brick in each column is c1, and the outermost brick color alternates going down the column.

Before beginning this problem, you should experiment with the test applet in the Test subfolder of the RectStairs folder. When you run the applet, a parameter window will be displayed that allows you to specify n, c1, and c2. Since there is no reset button on the applet, you will need to perform some other action to get the applet window to repaint itself with the new parameters when you change them. Such actions include resizing the applet window, closing and opening the applet window, expanding and shrinking the applet window, moving the applet window off the visible area of the screen and moving it back on, or covering and uncovering the applet window with another window. Note that the staircase always fills the rectangular area of the applet window, even when it is resized.

To complete this problem, you should flesh out the skeleton of the rectStairs method in RectStairs.java. Note the following:

• Use Java graphics (i.e., methods in the Java Graphics class) to perform all drawing.
• You may define any auxiliary methods you find helpful as part of solving the problem.
• Do not use any recursion (not even tail recursion) in your method definitions. All repeated patterns should be drawn using iteration expressed using while or for loops.
• When dividing the given rectangle r into blocks or drawing concentric rectangles on a given block, you will need to perform arithmetic that involves truncation or rounding of floating point numbers.
  • To truncate a floating point number n (which may be either a float or a double) down to an integer, use the cast (int) n.
  • To round a floating point number n (which must be a float and not a double) to the nearest integer, use the invocation Math.round(n).
  You may use either approach, although your pictures may differ in minor ways from the test applet depending on which approach you use. (The test applet uses rounding everywhere.) Do not worry about such minor differences. Even the results of rounding are not always very good -- for example, in the n = 10 example staircase, the nested rectangular patterns in the 7th, 8th, and 10th columns don't look so great.
• Test your method by running the RectStairs project. This will invoke your rectStairs with the graphics context and rectangle of the applet window using the n, c1, and c2 specified in the parameter window.

Task 2: Data Abstraction with Rects

Rects

A key idea in CS111 is data abstraction -- the notion that "users" can successfully use objects by understanding their contracts without knowing how the contracts have been implemented by the "implementers". Contracts not only serve to simplify the programming task for users, they also give implementers the flexibility to experiment with different ways to implement the same contract.

In Lecture 15, we studied the notion of multiple implementations of a data abstraction in the context of a simple rectangle abstraction known as a Rect. Conceptually, an instance of Rect is a rectangle positioned in the standard Cartesian coordinate system:

Here is a sample rectangle with lower left point (23,17), width 19, and height 11:

We emphasize that the rectangles we study in this problem are not the same as the java.awt.Rectangle class used in graphics applications, such as the Faces problem in Problem Set 9.

Below is a simple contract for the Rect class that supports two constructor methods and four instance methods. This class could easily be extended with more methods, such as methods for finding the perimeter or area of a rectangle, or returning its upper left and lower right points. But we've kept the contract small for simplicity's sake.

---

Rect Contract

Constructor Methods

public Rect (int llx, int lly, int width, int height);
Construct a rect from with lower left point (llx,lly), width width, and height height.

public Rect (Point ll, Point ur);
Construct a rect with lower left point ll and upper right point ur.

Instance Methods

public int width ();
Returns the width of this rect.

public int height ();
Returns the height of this rect.

public Point lowerLeft ();
Returns the lower left point of this rect.

public Point upperRight ();
Returns the upper right point of this rect

---

As an example, the rectangle depicted above could be created by either of the following constructor method invocations:

In the remainder of this problem, you will consider five different implementations of the Rect contract. In order to be able to discuss the different implementations, we will name them Recti, where i ranges between 1 and 5.

Task 2a

Point p1 = new Point (1,2);
Point p2 = new Point (9,6);
Rect1 a1 = new Rect1 (p1,p2);
Point ur1 = a1.upperRight();
Rect1 b1 = new Rect1 (ur1.y, ur1.x, a1.height(), a1.width());
Rect2 a2 = new Rect2 (p1,p2);
Point ur2 = a2.upperRight();
Rect2 b2 = new Rect2 (ur2.y, ur2.x, a2.height(), a2.width());

The purpose of this problem is to give you some practice drawing object diagrams. Recall that an object diagram shows a collection of interconnected class instances and arrays:

• Each instance is drawn as a large box that is labeled by the class name and contains the labeled instances variables of the class.
• Each variable is a small box that contains either a primitive data type (e.g., int, double, boolean, char) or a reference (i.e., pointer) to another object.

Follow these conventions in drawing your object diagrams:

• Every local variable and instance variable should be drawn as a small box with the name of the variable to its left.
• Each instance of a class should be draw as a large box labeled with the class name that contains the instance variables for that class.
• List nodes should be drawn as the two-slot boxes we have used in box-and-pointer diagrams.
• A variable that contains the null pointer should have a slash drawn through it.
• References should be indicated by drawing pointers rather than using reference labels.
• The arrow of a pointer should always point at an instance box or array box. It should never point to a variable box.
• Try to draw your diagram as neatly as possible. If you are not careful with how you lay out your boxes, your diagram will turn into "pointer spaghetti".

---

Implementation of the Rect1 class:

import java.awt.Point;

public class Rect1 {

  // INSTANCE VARIABLES --------------------------------
  private int llx;    // x coordinate of the lower left corner
  private int lly;    // y coordinate of the lower left corner
  private int width;  // width of the rect
  private int height; // height of the rect

  // CONSTRUCTOR METHODS -------------------------------

  // Construct a rect from the lower left (x,y), width, and height.
  public Rect1 (int llx, int lly, int width, int height) {
    this.llx = llx;
    this.lly = lly;
    this.width = width;
    this.height = height;
  }

  // Construct a rect from the lower left and upper right points.
  public Rect1 (Point ll, Point ur) {
    this.llx = ll.x;
    this.lly = ll.y;
    this.width = ur.x - ll.x;
    this.height = ur.y - ll.y;
  }

  // INSTANCE METHODS ----------------------------------

  // Returns the width of this rect. 
  public int width () {
    return width;
  }

  // Returns the height of this rect. 
  public int height () {
    return height;
  }

  // Returns the lower left point of this rect. 
  public Point lowerLeft () {
    return new Point (llx, lly);
  }

  // Returns the upper right point of this rect. 
  public Point upperRight () {
    return new Point (llx + width, lly + height);
  }

}

---

---

Implementation of the Rect2 class:

import java.awt.Point;

public class Rect2 {

  // INSTANCE VARIABLES --------------------------------
  private Point ll;   // lower left corner of rect.
  private Point ur;   // upper right corner of rect.

  // CONSTRUCTOR METHODS -------------------------------

  // Construct a rect from the lower left (x,y), width, and height.
  public Rect2 (int llx, int lly, int width, int height) {
    this.ll = new Point (llx, lly);
    this.ur = new Point (llx + width, lly + height);
  }

  // Construct a rect from the lower left and upper right points.
  public Rect2 (Point ll, Point ur) {
    this.ll = ll;
    this.ur = ur;
  }

  // INSTANCE METHODS ----------------------------------

  // Returns the width of this rect. 
  public int width () {
    return ur.x - ll.x;
  }

  // Returns the height of this rect. 
  public int height () {
    return ur.y - ll.y;
  }

  // Returns the lower left point of this rect. 
  public Point lowerLeft () {
    return ll;
  }

  // Returns the upper right point of this rect. 
  public Point upperRight () {
    return ur;
  }
}

---

Task 2b

Below are skeletons of classes Rect3, Rect4, and Rect5, each of which has one constructor method.

---

Partial Implementation of the Rect3 class:

public class Rect3 {

  // This declaration allows us to indicate all IntList operations
  // using the prefix "IL."
  private static IntList IL;

  public Rect3 (int llx, int lly, int width, int height) {
    coords = IL.prepend(llx,
              IL.prepend(lly + height, 
               IL.prepend(llx + width,
	        IL.prepend(lly, 
                 IL.empty()))));
  }

}

---

---

Partial Implementation of the Rect4 class:

public class Rect4 {

  public Rect4 (int llx, int lly, int width, int height) {
    area = width * height;
    ul = new Point(llx, lly + height);
    ur = new int [2];
    ur[0] = llx + width;
    ur[1] = lly + height;
  }

}

---

---

Partial Implementation of the Rect5 class:

public class Rect5 {

  public Rect5 (Point ll, Point ur) {
    sumsAndDiffs = new Point [2];
    sumsAndDiffs[0] = new Point(ur.x + ll.x, ur.y + ll.y);
    sumsAndDiffs[1] = new Point(ur.x - ll.x, ur.y - ll.y);
  }

}

---

Notes:

• The subfolder Rects of ps9_programs contains the implementations of Rect1 and Rect2 as well as the skeletons of Rect3, Rect4, and Rect5. You should flesh out the three skeletons.
• When you finish fleshing out a class, you should add the .java file for the class to the Rects.mcp project. You can do this via drag-and-drop (on the Macintosh), or via the Project:Add Files menu item (on both Macs and PCs)
• The RectTest class contains code that performs a simple test of the Rect1 and Rect2 implementations. It also contains commented out code that tests the remaining implementations. When you flesh out an implementation, you should uncomment the relevant testing code in RectTest. Compiling and executing the project file Rects.mcp will execute the main() method in the RectTest class and display the results of the tests in the Java Console window.
• The Rect3 has been configured with a declaration that allows you to refer to any of the class methods of the IntList by prefixing them with "IL.". For instance: IL.prepend, IL.head, IL.tail, IL.empty, IL.isEmpty.
• For Rect5, consider the following. Suppose there are two unknown numbers a and b, and you are given two numbers c and d such that c = a + b and d = a - b. How can you determine the value of a given c and d? How can you determine the value of b given c and d?

Task 2c

Point p1 = new Point (1,2);
Point p2 = new Point (9,6);
Rect3 a3 = new Rect3 (p1,p2);
Point ur3 = a3.upperRight();
Rect3 b3 = new Rect3 (ur3.y, ur3.x, a3.height(), a3.width());
Rect4 a4 = new Rect4 (p1,p2);
Point ur4 = a4.upperRight();
Rect4 b4 = new Rect4 (ur4.y, ur4.x, a4.height(), a4.width());
Rect5 a5 = new Rect5 (p1,p2);
Point ur5 = a5.upperRight();
Rect5 b5 = new Rect5 (ur5.y, ur5.x, a5.height(), a5.width());

Task 3: Morphing Polygons

A Note on Viewing Applets

This problem description contains an embedded Animation World applet. Experience shows that this applet may run fine in some browsers but not in others. If you cannot get the applet to work in one browser, try another one instead. If you can't find any browser that works, you can run the applet in CodeWarrior from the Test subfolder of ps9_programs/MorphingPolygon.

Task 3: Morphing Polygons

The following animation shows a single sprite that is a five-sided polygon that "morphs" (changes) over time. It behaves as if each corner of the polygon is a ball that bounces off the edges of the applet window:

The polygon in the above applet is created via the invocation new MorphingPolygon(5,Color.magenta), which specifies a magenta polygon with 5 points. The initial positions and velocities of the points are determined randomly every time the animation is reset. Test this by clicking the Reset button. There are many other ways to invoke the MorphingPolygon constructor, which are illustrated via other menu choices in the above applet:

• If the constructor method is supplied with true as a third parameter, the polygons will be drawn filled rather than unfilled. For example, try new MorphingPolygon(5,Color.blue,true).
• If only the number of sides is specified, it is assumed that the polygon is red and unfilled. For instance, try new MorphingPolygon(3).
• If only the color is specified, it is assumed that the polygon has four sides and is unfilled. For instance, try new MorphingPolygon(Color.cyan).
• If the constructor is called with zero arguments, a 4-sided, red, unfilled polygon is assumed. E.g., try new MorphingPolygon().

It is also possible to include several morphings polygons in the same animation, as in the Many Polygons menu option.

Your goal in this problem is to flesh out the definition of the MorphingPolygon class so that it describes sprites with the behavior shown above.

Notes:

• To flesh out the skeleton of the MorphingPolygon class, you will have to do the following:
  • Declare instance variables for the class. You should maintain the points of the polygon in an array of points and the velocities of the points in arrays dx and dy.
  • Declare constructor methods for the class. Your class should support all the different kinds of constructor methods discussed above. In particular, it should have the following five constructor methods:

    public MorphingPolygon (int n, Color c, boolean isFilled)
    public MorphingPolygon (int n, Color c) 
    public MorphingPolygon (int n) 
    public MorphingPolygon (Color c) 
    public MorphingPolygon () 
    

    Note that only the first constructor method definition should be nontrivial. The other four constructor methods should invoke the first constructor method using the this constructor notation presented in lecture.
  • Declare the following three instance methods required for any sprite:

    public void drawState (Graphics g)
    public void resetState ()
    public void updateState ()
    

• In order to randomly position the polygon corners within the walls and have these corners "bounce" off the walls, you need to know the dimensions of the canvas on which sprites are displayed. The upper left corner of the canvas is (0,0), and the width and height of the canvas can be extracted from the width and height instance variables of a Sprite (these are inherited by MorphingPolygon, which is a subclass of Sprite).
• Each time a MorphingPolygon instance is created or the resetState() method is invoked on a MorphingPolygon instance, the positions and velocities of the polygon corners should be randomly reset.
  • Use the class method invocation Randomizer.IntBetween(lo,hi) to choose a random integer between lo and hi, inclusive.
  • The randomly chosen position of a polygon point should be any point within the walls of the canvas.
  • The randomly chosen velocity of a polygon point should have dx and dy components that are between -20 and 20.
• The bouncing behavior of the polygon corners is very similar to that of the bouncing balls in the BouncingBall sprite studied in lecture 13. You should carefully study BouncingBall.java as part of doing this problem.
• To test your MorphingPolygon implementation, select the menu options in the the MorphingPolygonShowcase applet. A correct definition of MorphingPolygon will give rise to the same behavior shown in the test applet in the Test subfolder of the MorphingPolygon folder.

Extra Credit Opportunity: Open-Ended Animation [up to 10 points]

You can use AnimationWorld to create dazzling animations that show off your artistry and your programming talents. Here is a chance to be creative and earn some extra credit points at the same time.

For this challenge, build an animation of your own design. You may use existing sprites that we have studied, but you should create and use at least one new kind of sprite from scratch.

The MyAnimation subfolder of the ps9_programs folder contains a copy of the sprites and animations shown in Lecture 13. This is a good starting point for your own animations. You may edit the existing files or create ones of your own. Add any animations you create to MyShowcase.java.

Notes:

• The extra credit challenges are the only problems on this problem set in which you may collaborate with others in the class. Feel free to collaborate with as many people as you want.
• All extra credit assignments submitted will be posted on an "exhibition page" so that you can share your designs with the class.
• If you need help on any aspect of this challenge, do not hesitate to talk to the instructors.
• The amount of extra credit awarded on this problem will be proportion to the creativity and artistry in your designs, as well as the level of technical challenge. You can earn up to 10 problem set points in extra credit on this challenge. As an example of an animation worth 10 points, see Erin Stadler's Fall'99 animation. Some student animations from Spring '03 can be viewed in the Animation gallery.