Drawing of the shapes

For this programming project, three shapes are required. Two of them must be a Sierpinski triangle and an H shape. The third one is your choice, though it must be a fractal-like shape. You can get some ideas by consulting this page.

The Sierpinski triangle starts with one triangle. We call this level 1 of the triangle. At level 2, 3 triangles are added inside of the first triangle. At level 3, 3 more triangles are added inside of the three level 2 triangles. Mathematically, the process goes on forever. For our display, this is of course not possible since we are limited by the size of single pixel on the computer screen. We will limit the level to a maximum value of 10 for the Sierpinski triangle.

Level 1: 1 triangle	Level 2: 1 + 1 * 3 = 4 triangles	Level 3: 1 + 1 * 3 + 3 * 3 = 13 triangles

The H-shape follows the same pattern as the Sierpinski triangle.

Initially, at level 1, there is one H. At level 2, 7 H's are drawn within the seven squares making up the original H. And at level 3, 7 more H's are added in the 7 seven H's of level 2. As for the Sierpinski triangle, we need to limit the level to a maximum value, which will be 5 for the H shape.

Level 1: 1 H	Level 2: the shape has 1 + 1 * 7 = 8 H's (but only the last level is drawn since the level 1 H would hide the smaller H shapes)	Level 3: the shape has 1 + 1 * 7 + 7 * 7 = 57 H's (though only the level 2 H's are displayed)

Organization of the shape classes

Since the 3 shapes that are displayed have many features in common (e.g. all of them may add a level or remove a level), we want to use inheritance to avoid code repetition. To do so, we start by listing all of the common methods in a Shape interface. As an aside, notice that the code of FractalDisplay knows only about the Shape type except for the actual constructor calls of the concrete shape classes. This is of course the advantage of using inheritance. It creates a low coupling between the FractalDisplay class and the concrete shape classes, that is the code of FractalDisplay doesn't rely heavily on the implementation of the Shape interface by the concrete shape classes.

The Shape interface will contain the following methods

When thinking about the implementation of the Shape interface by the concrete shape classes, you will notice many similarities between all of the implementations. For that reason, it is a good idea to create an abstract class AbstractShape that implements Shape and contains the code that is common to all three concrete shape classes. By inheriting AbstractShape, the concrete shape classes get the methods implemented in AbstractShape and just need to add their own specific code (e.g. the implementation of the draw method). This is leading us to the following class hierarchy:

As just mentioned, AbstractShape will contain the fields and methods that can be used by all of the concrete shape classes. For instance, all shapes have a level, a maximum level value, a color, and may have children shapes (e.g. any Sierpinski triangle may have 3 inner triangles, and any H may have 7 inner H's). A possible design of AbstractShape would list fields to store that information. For instance:

public abstract class AbstractShape implements Shape {

protected int level;
protected int maxLevel;
protected AbstractShape[] children;
protected Color color;
// The fields may be initialized by the AbstractShape constructor with the values
// received from the super() calls in the constructors of the concrete shape classes.
// For instance, the SierpinskiTriangle constructor may call the AbstractShape constructor with
// the a max level value of 10 and a children array length of 3
// Alternatively the fields may be initialized in the concrete class constructors (they are visible by
// the concrete classes since they are declared protected)


What precisely goes in the AbstractShape class depends on your implementation design, though I strongly recommend that you follow the guidelines given in the next section. In any case, make sure that you avoid any code repetition among your implementations of the concrete classes. It is possible to have all of the methods of the Shape interface implemented by AbstractShape except for the draw method (and possibly the update method if you attempt the extra credit part).

Implementation details

The details outlined below use the HShape and SierpinskiTriangle classes as illustrations. However, they should be readily applicable to the fractal shape that you select as your third shape (coded in the MyShape class).

addLevel() method (must use recursion)

As mentioned in the previous section, it is possible to implement the addLevel method in the AbstractShape class. The only addition to a concrete class can just be a method to create the actual child shapes.

To model the Sierpinski triangle, we can think of the triangles at level n as being the children of the triangle at level n-1. For instance, for a Sierpinski triangle with three levels, the level 1 triangle has three children which are the three level 2 triangles. Each of the three level 2 triangle has also three children on level 3, for a total of nine triangles. And the nine triangles at level 3 have no children since they are on the last level.

For the H shape, a division can be thought of creating a covering of 7 smaller H's for every H making up the shape. That is we can think of an HShape has having 7 children.

Even though the construction of the Sierpinski triangle and the H are different, we can use the same approach for both and write some of the code in their common AbstractShape base class.

In the AbstractShape class, add an array of AbstractShape objects to store the AbstractShape objects that are the child shapes. For example, the array will be of length 3 for a Sierpinski triangle and of length 7 for an H shape. The array may be initialized in the constructor of AbstractShape if the AbstractShape constructor takes the array length as a parameter, or directly in the constructor of the concrete classes if you make the visibility of the array protected. The elements of the children array are null for an initial fractal. When level 2 is created, the array is filled with actual shapes. For level 3, it is the arrays of the shapes that are added at level 2 that are filled, etc.

In the AbstractShape class, implement the addLevel() method to add a level to a shape. It will do so by initializing the elements of the array of children for the last current level. In the FractalDisplay class, you can check that the method is called whenever the "Add level" button is clicked. Since the FractalDisplay class has only a reference to the top level shape, the method will iterate to get to the last level of the shape. Do so by using recursion (don't use any loop, except to loop over the elements of the array of children in a current level.) The base case of the method will be attained when the array of children is empty. Fill the array of children by calling a method (e.g. createChildren()) declared abstract in AbstractShape and implemented in the concrete shape classes. Dynamic binding will automatically select the correct implementation! Of course, the array should be filled only if the maximum level has not been reached. Return a boolean to tell it if a new level could be added. The boolean value is relayed to the FractalDisplay class to tell it if the operation was successful. If a new level could not be added, then the FractalDisplay displays a message box saying that no new level can be added.

removeLevel() method (must use recursion)

In the AbstractShape class, implement removeLevel() to remove a level from a shape. If a shape has n levels, the last level may be removed by setting to null the elements of the array of children at level n-1. This method is called by the DisplayFractal class whenever the button "Remove level" is clicked. Contrary to the addLevel method, removeLevel won't iterate to the last level of the selected shape. It will iterate to the level preceding the last level. This is because to remove the last level, the method needs to set to null the elements of the array of children that refer to that last level. As for addLevel, iterate by using recursion (that is don't use any loop, except to loop over the elements of the array of children in a current level.) If the shape that is displayed is at level 1, a level can't be removed. In that case, removeLevel returns false. The boolean value will be passed on to the display so that it can display a message box if a level could not be removed.

countShapes() method (must use recursion)

In the AbstractShape class, implement countShapes() to count the total number of shapes in a shape. If there is only one shape (level 1), the count is 1. For a shape with two levels, the count is 1 + number of shapes at level 2, that is 4 triangles for a Sierpinski triangle with two levels, or 8 H's for an H with two levels. For a shape with three levels, the counts are 13 for a Sierpinski triangle and 57 for an H.

As for addLevel and removeLevel, your implementation must use recursion except to loop over the children shapes in a current level.

The countShapes() method is called from the FractalDisplay class whenever the mouse is right clicked on a shape.

draw() method (must use recursion)

This is the method that must be implemented in each concrete class (SierpinskiTriangle, HShape and MyShape). The method takes a Graphics object that can draw almost anything. Check the documentation of the Graphics class in the java documentation pages. For example, the Sierpinski triangle may be drawn by invoking the drawPolygon method.

As for all of the other methods discussed in this section, use recursion to implement the method except to loop over the array of children.

Extra-credit (up to 3 points)

Implement the update() method that takes an integer in the 0-100 range and modifies the display of the current shape as a function of the value of the integer. The value is changed by moving a slider on the display window. Initially the value given by the slider is set at 50. As an illustration, here is an example with the Sierpinski triangle.

Slider = 50	Slider < 50	Slider > 50

Advice

• Make changes incrementally and test along the way.  Also, draw pictures, do pseudocode design, draw object/class diagrams, plan, plan, plan.
• Make sure you don't repeat code among the concrete shape classes.
• Make sure you are using recursion for addLevel, removeLevel, countShapes, and draw.
• Document all of the methods that you write (use javadoc conventions).

Written Report

1. Planning and operation: What does your program do?  Describe the major features.  If you worked with a partner, how did you divide responsibilities?
2. Implementation:  How is your program organized?  What are the major classes?  How do the classes interact? Draw a class diagram.
3. Give a clear explanation of the recursive algorithms to add a level to and remove a level from a shape.
4. Testing:  How did you test your code?  What sort of bugs did you encounter?  What works and what doesn't?  Are there any unresolved problems in the code?
5. Turn in your report as a pdf file along with your java files on the turn-in page.

Individual evaluation report (turned in on Canvas)

Evaluate this project:

• What did you learn from it?  This could include things you learned about specifications and interfaces, design issues, Java language issues, debugging, etc.
• Was it worth the effort?  
• If you worked with a team member, did you feel that all team members contributed equally to the project?

Checklist: a summary of the important points of this assignment

• Shape interface: as listed above
  
  
• AbstractShape class: a protected instance field for the array that stores the children of this Shape, implementations of addLevel, removeLevel, countShapes (with recursion for all)
  
  
• SierpinskiTriangle/HShape: implementation of draw
  
  
• MyShape: a class to display a fractal like shape of your choice. The implementation is similar as in HShape and SierpinskiTriangle.
  
  
• Report: submit your report as a pdf file.
  
  
• Individual report: submit your report on Canvas.