Lab 7: Sierpinski Fractals and Recursion

Lab Overview:

Fractals are non-regular geometric figures that have the same degree of non-regularity on all scales. In this lab, you will build a fractal named after Waclaw Sierpinski. You have seen this fractal before. Although the implementation of Sierpinski fractal covered in class was a recursive implementation too, in this lab you will write an applet to draw the same Sierpinski applet with some added features.

Before you begin with the lab:

Check if your P: Drive and H: Drive show up!

For help regarding Eclipse, refer the Lab3. If your computer doesn’t show the P: drive or if Eclipse isn’t working, (Some error saying, Workspace already in use), for both these problems, run the afsdrivemapxp.vbs file as follows.
(Do the following ONLY if your P: Drive, H: drive or Eclipse are not working.)

Go to Start -> Documents -> afsdrivemapxp.vbs and click on that file.
Your network drives (P, H and Q) should appear!

If you don’t see the afsdrivemapxp.vbs file at the above mentioned path, search for it on your C: drive and you should find it.

Sierpinski Fractal:

The Prelab should help you find the sequence followed when choosing the vertices for the triangles given the vertices of the larger (containing) triangle.

1. Draw an equilateral triangle using points x, y, and z
2. Create three more Sierpinski fractals, each with the following vertices
   • x, midpoint(x,y), midpoint(x,z)
   • y, midpoint(y,x), midpoint(y,z)
   • z, midpoint(z,x), midpoint(z,y)

As you might notice, the algorithm results in infinite recursion. It is recursive because the algorithm for drawing a Sierpinski fractal includes drawing another Sierpinski fractal. The algorithm is infinite because there is no base case. In theory, fractals are infinitely recursive, but in practice the recursion continues only a set number of steps, or until further recursion does not noticeably change the image. In our case, the algorithm is very similar to the theoretical algorithm:

  void sierpinski(Point x, Point y, Point z)

1. Draw a triangle using points x, y, and z
2. If number of steps is greater than  zero
   then reduce the number of steps and create three more Sierpinski fractals, each with the following vertices
   • x, midpoint(x,y), midpoint(x,z)
   • y, midpoint(y,x), midpoint(y,z)
   • z, midpoint(z,x), midpoint(z,y)

Try to use the algorithm to draw on paper a third generation Sierpinski fractal (in the incremental order followed by the algorithm.). Your final sketch should look like the one above. If you can't draw it at this point, it might be a good idea to reread the algorithm or ask a TA to help explain it.

In this lab, instead of using a FIXED value for "Generations", your applet should allow the user to input the value. (Note that this value, specified by the variable limit was fixed to 10, in the Sierpinski applet covered in class.) Also instead of using integer pairs as the x and y co-ordinates of the triangle vertices, you will use a standard Java class designed specifically to handle co-ordinates, Point.

Point is a Java class that stores an x and a y value (a coordinate pair).
For example:
Point p1,p2,p3;
p1 = new Point(5,6);
p2 = new Point(10,20);
p3 = p1;

The Point class allows you to access the individual data members in its object.

p1.x = 10;
p3.y = p1.y/2;
z = p2.x;

One of the basic ideologies of  Object Oriented Programming (OOP) is that instances in a program (instances = variables in procedural languages and Objects in OO-languages) should represent the real world entities with higher fidelity and ease. Dealing with 3 vertices of a triangle as 3 Point objects in your applet is much more convenient and closer to the real world as compared to dealing with 6 integers or floating-point numbers.

The Point class has a lot of methods, a programmer can use when dealing with co-ordinates. You can refer to the API of the Point class for details. (http://java.sun.com/j2se/1.3/docs/api/java/awt/Point.html ) 

The Implementation:

1. Start/Launch Eclipse and create a new project called lab7.
2. Import the ModelAwb.jar file from the course website.
3. Delete the text in the Model.java and rename it as SierpinskiExtended.java.
4. You can refer to the Sierpinski.java covered in class as the basic skeleton ,but you will not need many of the features used there.
5. Your applet will only have ONE button, "Draw Fractal" and one IntField "Generations" to input the number of generations of the fractal the user wishes to see.( You should delete the extraneous buttons  and the code associated to them in the actionPerformed and init methods. )
6. In this lab, you will have to write a new sierpinski function and the actionPerfomed method


  a. public void sierpinski(Point p0, Point p1, Point p2, int numTimes)
      (This is the recursive function.)

1. Check to see if the number of generations (numTimes) is greater than ONE.
   
2. If yes, continue to step iii. directly; Else draw the triangle, using the drawTriangle method. (This drawTriangle method will only have three drawline statements and a return) and return to the calling function.
3. Find the three midpoints (of the 3 edges of the triangle)
4. Recursively, call the sierpinski function 3 times. (for the 3 triangles to be drawn inside the containing/bigger triangle. Reduce numTimes by 1 while passing it as a parameter).
5. return to calling function.

NOTE: Can you spot the difference between this sierpinski function and the one you saw in class?
This difference is in the base case of the recursive function. Can you elaborate on how this affects the sequence in which the triangles forming the Sierpinski Fractal is changed?
(Extra points for including as TEXT in the body of the index.html file you have in this project.)

         b. public actionPerformed (actionEvent event)
             In this method, the only action you need to perform is if the "Draw Fractal" button has been pressed. If yes,

1. Clear the screen (use the DrawingPad clear() method).
2. Create three Points.
3. Get the number of generations from the IntField "Generations".
4. Call the sierpinski method that you have created with the 3 Points (from step ii.) and "Generations" as parameters.

7. Save changes you made to the file, build it (if needed) and run it in Eclipse.
8. Ensure that your applet works with all critical values of "Generations".
   (Note: If you simply follow the above instructions, your applet will not work under certain values of "Generations". What are these ? Include an answer to this in your index.html file, as well. )
9. Change the code/algorithm (sierpinski( ) ) above to ensure that your applet doesn't fail with these "critical" value(s). (HINT: The change is ADDING one more "if" statement. Don't change anything else.)
   
10. Once you are sure the applet is working correctly. Make changes to the index.html file to change the applet code to point to SierpinskiExtended.class.
11. Finally export the project to the file system (to the P:\public_html\cps1\ folder) and check if your applet works over the WWW at www.duke.edu/~xyz99/cps1/lab7/

Wrapping up:

If you don’t complete this lab NOW, please make sure you have saved all the right files in the P: drive (if any) and in Eclipse. Files on your desktop, including the ModelAwb.jar file will not be permanent. When you do work on the project again, if you have imported the ModelAwb.jar file properly, you will NOT need to download it again from the course webpage and import it again. All your Eclipse files, created by Eclipse on the H: Drive will also be permanent and hence, so will be your labs (Projects).

REMEMBER, for this lab, in addition to the applet above, you are also required to include answers to the  two questions in steps  6 and 8 in your html file (P:\public_html\cps1\lab7\index.html file).

Also, once you are done, remember to modify your CompSci 1 webpage, (i.e. the index.html file you created as lab1, in your P:\public_html\cps1\ folder.) by adding a link to the applet you just created.

Siddhesh Sarvankar. (siddhesh@cs.duke.edu )