Mandelbrot

The Mandelbrot set is a set of complex numbers that remains bounded (does not increase to infinity) when iterated with a quadratic polynomial function. When the set is graphed on the complex plane, the set boundary has a complex pattern that does not simplify at any magnification and is therefore sometimes defined as a fractal.

Setup

Create a directory assignment7 under assignments in your cs170 directory. All code for the assignment should be stored in this directory. 

cd ~/cs170/assignments
mkdir assignment7
cd assignment7

Details

The first part of this assignment is the creation of a class that represents complex numbers. Complex numbers are of the form (a+bi), where i is the mathematical imaginary number. For Mandelbrot, you will be required to have three operations: addition, multiplication, and magnitude (euclidean distance from the origin for the complex number). We will discuss in class how you can add, multiply, and compute the magnitudes.

Create a program that draws an image of the Mandelbrot set for complex numbers in the range -2 < a, b < 2. To draw the set using Tk, you will need to convert canvas pixel x, y coordinates to complex a, b coordinates. For example, if the canvas is 200 by 200 pixels, the pixel (0, 0) would map to the complex coordinate (-2, -2) and the pixel (100, 100) to the complex coordinate (0, 0). For each pixel in the image set the color to a shade of gray depending on how many iterations of the quadratic polynomial function were required for the complex number's magnitude (absolute value) to exceed 2. The quadratic polynomial function can be defined recursively as:

cn = cn-12 + c0

Where c0 is an initial complex number, that corresponds to a pixel in the image, and cn is the nth complex number computed with the quadratic polynomial function. Note, since 255 is the largest number that can be represented with a gray-scale color, 255 is the maximum number of times that you need to iterate the quadratic polynomial function. For example, if the quadratic polynomial function is iterated 100 times before the absolute value becomes larger than 2, then set the pixel to be the color with the RGB values (100, 100, 100).

The real beauty of the Mandelbrot set is not the full image, but the inherent recursive structure that becomes apparent as you zoom in on pieces of the set. For this, you will want to write your functions that compute the set in such a way that the user can specify what locations to "zoom" in on within the image. Your program will read in the range in which to render the Mandelbrot set. For example: 

$ cat mandel_input_1
0 0 4
$ python3 mandelbrot.py < mandel_input_1

Will render the entire mandelbrot set, which is what you see above. In general, the input should read a single line consisting of 3 integers: the center x, center y, and the width of the square being rendered.

In order to implement this, the program should store the range of complex numbers that are currently being rendered in class attributes. The program should also have a method that converts pixel coordinates to complex coordinates using the current complex range instance variables. The following equations will convert between pixels coordinates and complex complex coordinates in a specified range:

ca = px / W * (maxa - mina) + mina
cb = py / H * (maxb - minb) + minb

Where c is the complex coordinate that corresponds to the pixel coordinate, p, W and H are the width and height of the window, and min and max are the current complex range of values.

Make sure you play around with different generations of the Mandelbrot set. Include a screenshot of your favorite image with your code submission. Make it a good one, because the best image in the class (as selected by an on-line poll) will be hung on my office door, and displayed on the course website. For the purposes of the competition, you should generate large images, on the order of 1000 x 1000 pixels.

Submission

You are required to submit a tar file to http://cseval.roanoke.edu/. On cseval, there is a link for Assignment 7. You can create a tar file by issuing the following commands: 

cd ~/cs170/assignments
tar czvf assignment7.tgz assignment7/

"Hacker" Prompt

  1. Color Map: It is possible to create more visually pleasing images by using a color map to specify what color maps to which escape value. It is possible, for example, to have a color map between colors with RGB values (100, 255, 150) and (200, 50, 0) by interpolating between the two colors based on the escape value. It is possible to interpolate by using the equation from bezier, but use it with each of the color channels. For example, if the escape value is 128, then the interpolated color of the above two colors would be:

    r = (100 * (1 - i)) + (200 * i)
    g = (255 * (1 - i)) + (50 * i)
    b = (150 * (1 - i)) + (0 * i)

    where i = 128 / 255.

    It is also possible to produce a color map with more than two colors by first determining which pair of colors an escape value is between, and then interpolating the colors. For example, if a color map consists of three colors and the escape value is 42, then because 42 / 255 is less than 0.5 the interpolated color would be produced by interpolating between the first and second colors with i = 42 / 127.

  2. Click, Click, Zoom: As you will no doubt be able to see, trying to find interesting locations in the Mandelbrot set with the above zoom capabilities is going to be difficult. You will have to manually convert from image pixels to complex numbers, and determine the zoom factor the same way.

    However, there is an easier way. But it involves click handlers. Define a click handler that can get the location the user wishes to zoom in. You can also assume that each click will zoom in by a factor of 2. For the first click, the size of the complex plane becomes 2, ranging from (-1, 1) in both directions. You could also add a click handler for right clicks, which will zoom out, doubling the size of the square being generated.

    This process will be faster than manually determining where to zoom, but is still is not going to be quick. Be prepared to wait several seconds (or minutes) between each click to see the new zoomed in location. The code for this, however, is pretty easy to implement.

  3. Saving: If you do the above click handler, you might want to be able to save the location that you just generated. It will make getting back to that location much easier. You could also add some code that would automatically generate an image for you, instead of having to take a screenshot!

    Look at the documentation for the Menu widget of Tk. Add two options on this menu: Save coordinates and save image. Save coordinates should save the current coordinates to a file that your program has specified. Save image should save the image currently on the canvas to a file you have specified in your program. Note: The way this is defined, you can very easily overwrite previously generated information. Be careful!

    4. Last modified: Mon Mar 10 10:20:21 EDT 2014