## CS 101 (Fall 2000) Lab 5: Iteration -- Mandelbrot Set

Authors: Sergey Klibanov and Ron K. Cytron
Lab Assigned Design Due
(In class)

1 PM
Implement
(In Lab)
Demo
(In Lab)
Lab Due
(In class)
Friday
1 PM
3 Oct 6 Oct 11-12 Oct 18-19 Oct 23 Oct

### Overview:

Fractals are mathematical models that can create seemingly complex drawings from very simple specifications. Because they are not easily bored, computers are well-suited to iterative tasks. You will use iteration in this lab to compute a fractal drawing. This lab emphasizes how computation can be applied with relative ease and speed to create what would take a human much longer to accomplish.

### Goals:

By the time you are finished with this lab, you should have:
• An understanding of how to use the JavaDoc tool
• A better understanding of iteration and fractals
• Experience translating from one coordinate system into another
• Experience documenting the API for some simple classes
• More experience with recursion (if you do the extra credit)
• An appreciation for how easily a complex calculation can be described mathematically

### Before Starting:

1. Make sure you understand how to use the JavaDoc tool.
3. See the wallpaper a student made from this lab.
4. Take a look at the JavaDoc for this lab
5. Study the setPixel method of PictureComponent
6. Study recursion and iteration examples given in class.
7. Run the sample solution. Be sure to examine the text output as well as the pretty picture. Doing this will help illustrate coordinate conversions.

Zip contains:
``` Lab5.java Mandelbrot.java Startup.java Point.java ZoomingListener.java ```

### Background Information:

Fractals are an amazing mechanism for describing complex systems in terms of simple and recursive components. The idea of fractals in the complex plane (where the x coordinate is real and the y coordinate is imaginary) dates back to 1918, when Gaston Julia began research that characterized Julia Set fractals. In 1979, Benoit Mandelbrot defined a map over Julia sets that reflected the expense of computing a specific point in the set. Such maps generate interesting patterns, and we will in a sense reproduce Mandelbrot's work in this lab. Since Mandelbrot's original work, computers have become faster and Java has made programming them easier. Thus, our renditions will be more aesthetically pleasing (and won't take overnight to render either). Search here (using Google) to find some pages with more background information.

### Problem statement: Drawing a Mandelbrot Set

This lab involves computation over some points of a complex plane. Recall that a complex number has two components: a real and an imaginary part. For each complex point `c` that we want to display, we compute the function `rigor(c)` as follows.

Pseudocode for rigor(c):

• `z=c`
• `iters = 0`
• `while abs(z) < 2 and iters < maxIters`
• `z = z*z + c`
• `iters = iters + 1 `
• Return `iters` as the answer
In other words, `rigor(c)` is the number of iterations that it takes to compute the value at `c`. The value of `maxIters` is arbitrary, but let's assume for now that 100 iterations are allowed for the computation. The function `abs(z)` computes the distance of `z` from the complex point (0,0).

To show complex numbers on an x-y axis system, let us assume that the real component of a complex number is registered on the x-axis; the imaginary component is thus registered on the y axis. If we apply the above computation over the complex plane as x ranges from -2 to 2 and y ranges from -2i to 2i, we obtain the following picture.

 Figure 1: Initial display (-2, 2i) (0, 2i) (2, 2i) (-2, 0i) (2, 0i) (-2, -2i) (0, -2i) (2, -2i)

You should see something similar when your working lab first starts up. The black areas represent points whose computation exceeded the limit set above (`maxIters`). In the figures shown in this write-up, the color of a non-black point c is computed as the hue-shift away from `Color.blue` However, you are free to pick your own function for the color. by the value of `7 * rigor(c)`.

What is really interesting about a fractal drawing is that one can dive into the drawing and discover ever increasing detail. Below you see the results of zooming into the picture.

 (-1.6, 0.4i) (0.7, 0.4i) (-1.6, -0.5i) (0.7, -0.5i)
 (-1.5, 0.06i) (-1.4, 0.06i) (-1.5, -0.06i) (-1.4, -0.06i)
Zoom on left black circle Zoom in further to the left of black circle
Zooming into the picture changes the fractal plane coordinate of the pixels. Part of what you must implement for this lab concerns the mapping between the fractal plane and the pixels on the screen.

### Design

Since this is your first design experience, we will describe what is needed for the one class you must design for this lab. The other classes are described in the usual documentation .

For the class you design, you are to submit the API, in JavaDoc printout. Here is how to do that.

1. Unzip and install the software for this lab as usual.
2. Using the descriptions below, create a `Complex.java` file that contain stubs for the methods in your API. A stub is simply the method definition (return time, name, parameters) along with a simple `return` statement if needed. For a stub, such returns can return 0, null, etc.---whatever seems appropriate.
3. Make sure your stubs compile correctly along with the class software.
5. Use the `JDE` menu to generate the JavaDoc for the entire lab.
6. Print out and turn in only the pages for `Complex`.
`Complex`
• This class represents a complex number.
• Instances of this class are immutable.
• You will need to add, multiply, and subtract complex numbers. Your approach should be object-oriented! In other words, to add two complex numbers, you should not make a method ``` Complex add(Complex c1, Complex c2) ``` Instead, you should make a method called on one complex number, passing the other one is as a parameter. The result of the call should be a new complex number (because instances are immutable) that is the sum of the two.
• Finally, you will need to compute the absolute value of a complex number as its (Euclidean) distance from the complex point (0,0).
For ideas on how this will be used, you can take a look at the documentation for the classes that you are not designing.

### Approach

1. Create an immutable Complex number class capable of addition, multiplication, and taking the absolute value (distance of number from (0,0). The names for your methods should be based on your API.
• A common way to represent complex numbers is a+bi, where i is the square root of -1. Simply store a and b.
• To add two complex numbers, simply add their respective real and imaginary components.
• To multiply two complex numbers, simply perform polynomial multiplication on the operands. Remember, `i2=-1`
• To calculate the absolute value of a complex number, compute the Euclidean distance of the complex number from the origin (0,0). For example, the absolute value of 3+4i is 5.
2. Test your `Complex` class from `Startup`. Be sure to exercise all of your methods and print out the results. The testing code should make it obvious that your `Complex` class works, by emitting messages to `Transcript` such as:
(2,3i) + (5,-8i) = (7,-5i)

3. Take a look at `ZoomingListener` to see under what conditions it affects `Mandelbrot`.
4. Read over the description of how to draw the current Mandelbrot set, described at the end of this write-up.
5. Implement `Mandelbrot` without zooming. Your picture should look like the one at the beginning of this write-up.

Hint: Place the code that actually creates the drawing in a method so it can be called whenver the displayed drawing should change. For example, zooming will affect what is displayed.

6. Implement `zoomto(Rect r)`. This method is called for you when you drag a rectangle in the display.
7. Implement the other zooming methods. You get full credit for these methods only if you have them call `zoomto(Rect r)` with the appropriate rectangle. Duplicating code to achieve `zoomin` and `zoomout` will cost you points!

### Implementation of `Mandelbrot`

• The size of the display does not change as your program runs.
• You will need a method to map a given pixel in your display to its corresponding point in the complex fractal plane.
• Originally, the displayed area is mapped so that its lower-left corner corresponds to (-2,-2i) and its upper-right corner corresponds to (2,2i).
• As the user zooms in and out, the correspondence between the pixels and the fractal plane changes. For example, the center of the displayed area may not always correspond to the fractal coordinate (0,0), although it did when the program first started.
• The display is managed by a single PictureComponent object. The pixel at (a,b) can be can be set to a particular color with its `setPixel(int a, int b, Color c)` method.
• When converting display (`PictureComponent`) coordinates into fractal plane coordinates, keep in mind that the vertical coordinate increases in the down direction for the display but increases in the up direction for the fractal plane.
• To illustrate the mapping from display-pixel coordinates to fractal-plane coordinates, here is an example for one pixel. In this example, we express display-pixel coordinates in brackets and fractal-plane coordinates in parentheses.
1. Suppose a display of 300x300 pixels has just been created. Then the mapping is in its initial state as shown in Figure 1:
• The lower-left corner pixel [0,299] correponds to the fractal-plane coordianate (-2,-2i).
• The upper-right corner pixel [299,0] corresponds to the fractal-plane coordinate (2,2i).
2. Consider now the pixel at display coordinate [40,120]. We want to convert this particular pixel to its fractal-plane coordinate (x,y).
x coordinate
1. The display's x-axis is 300 pixels wide, while the corresopnding fractal plane represents reals from -2 to 2.
2. We must make a proportional conversion from screen coordinates to fractal coordinates. The x coordinate of the pixel is 40. The fraction of the entire x length of the PictureComponent of 40 is 40/300, or about .133.
3. In the displayed portion of the fractal plane, the x-axis stretches from -2 to 2, making the width (2-(-2)) or 4.
4. Applying the fraction of the pixel to this width, we compute
`0.133 * 4 = 0.532`
That is how far we are from the minimum x value in our fractal plane. Our fractal plane's x axis starts at -2, so
`-2 + 0.532 = -1.468`
is the value of x in the fractal plane that pixel.
y coordinate
• The same logic is applied to the y-axis, which represents imaginary coordinates between -2i and 2i in Figure 1.
• Keep in mind that the display's y-axis increases in the downward direction, while our fractal plane's y-axis increases in the upward direction. In other words, the display coordinates increase from 0 to 299 as we move from top to bottom; the corresponding fractal-plane coordinates in Figure 1 decrease from 2i to -2i as we move from top to bottom.
• We leave it to you to figure out how to do this; ask for help if you need it.
3. The pixel coordinates [40,120] convert to (-1.468, 0.4i) in the fractal plane.
4. We now illustrate the operation of `rigor(c)`, whose pseudocode is presented above.
1. We supply `rigor` with the fractal coordinate
`c`=(-1.468, 0.4i)
2. `z` is set to `c`.
3. We check whether `abs(z) < 2 `
4. Because `abs(z)=1.52`, we can proceed.
5. We apply the equation `z=z*z+c` to obtain
`z=(0.52, -0.77i)`
6. We compute `abs(z)=0.93`, which is less than 2, so we continue.
7. We recompute `z` and obtain
`z=-(1.79, -0.41i)`
8. We compute `abs(z)=1.84`, which is less than 2, so we continue.
9. We recompute `z` and obtain
`z=(1.57,1.87i)`
10. We check whether `abs(z) < 2`
11. Because `abs(z)=2.44`, which is not less than 2, we are done.
12. We performed 3 iterations, so `rigor` returns the value 3.
13. We now choose a color for the pixel at [40,120] based on the number 3.
• You will notice that the given `ZoomingListener` class takes care of the user interface. All you have to do is fill in the methods it calls in `Mandelbrot`.
• Each pixel of the image needs to have a certain color assigned to it. Here is how to calculate that color for a particular pixel `p`.
1. First, convert the `p` to a fractal-plane coordinate `c` as described above.
2. Compute ` n = rigor(c)` as described above.
3. The value of `n` represents how many iterations `rigor` spent before it returned.
• If `n < maxIters`, then the pixel at `p` should be set to a color using some inventive scheme, using `PictureComponent`'s `setPixel` method.
• Otherwise, the iteration limit was exceeded and the pixel's color should be set to black. We want the color to be some function of n. One idea is to pick a base color, and then shift its hue by some function of n. For more help on this matter, see the documentation or ask for help.

#### Required features

The user should be able to
• Use the up and down arrow keys to increase and decrease the iteration limit by factors of 2 and .5, respectively.
• Use the left and right keys to zoom out and zoom in (respectively) to the center of the current window.
• Zoom into a specified part of the image by dragging a rectangle from the area's upper-left corner to its lower-right corner.

#### Extra credit

• The Mandelbrot set has a property such that, inside the set (within the range mentioned above) if there is a rectangle with its edge all the same color, the body of the rectangle will also be that color. Using this property will speed up rendering dramatically in some cases. Use a recursive method to take advantage of this property.
• This method speeds up rendering by reducing the need to calculate the same color hundreds of times to achieve a simple monotone. A hint: if you redraw() every time you change the image, rendering will slow down dramatically. The sample solution, which uses this technique, only redraws on the 3rd level of recursion. However, during debugging, redrawing after every change is probably a good idea.
• One of the requirements for this method to work is that the rendering rectangle be inside the initial rectangle shown in Figure 1. You should have at least a minimal amount of checking for this before you proceed to use the recursive method. Otherwise, default to the slower purely iterative process.

### What to turn in:

1. Complete a design cover sheet for turning in the API for `Complex`. Attach the JavaDoc printout for `Complex`.
2. Complete a code cover sheet.
3. Provide a printout of any files you have modified.
4. Provide a transcript from Startup's textual tests on your classes. Recall that this file is produced automatically by the Transcript and can be found in the file `transcript.txt` in the same folder as your Lab 5 files.