Write a C program to generate a PostScript program that will plot the Mandelbrot set.

The Mandelbrot set a specific set of points on the plane with many fascinating properties. One can determine whether or not a point (x, y) is in the Mandelbrot set by performing the following calculation: start with r = x and s = y, then enter into a loop which resets r to r*r - s*s + x and s to 2*r*s + y (using the old values of r and s in both of these update formulae). If this sequence remains bounded (neither r nor s goes to infinity) then the point (x, y) is in the Mandelbrot set; otherwise, if the sequence diverges to infinity, it is not. If you plot the points in the Mandelbrot set black, and those not in the set white, a strange and wondrous pattern emerges, roughly within the 2.0-by-2.0 box centered at (-0.5, 0). For a more dramatic picture, you will replace the white points with color gradations, depending on the number of iterations needed to discover that the point is not in the set. These colors reveal the striking detail of the terrain just outside the Mandelbrot set.

Part 1: Mandelbrot computation. Your first task is to write a function that determines whether or not the point (x, y) is in the set. The mathematical definition of the Mandelbrot set is precise, but is computationally unappealing, since we would have to perform an infinite number of iterations to determine whether a single point is in the set! We are rescued by the following mathematical fact: if r*r + s*s ever gets to be greater than 4, then the sequence will surely diverge off to infinity, and the point (x, y) is not in the set. There is no simple test that would enable us to conclude that (x, y) is surely in the set, but if the number of iterations exceeds 255, the point is extremely likely to be in the set.

Write a function int mandel(double x, double y) that performs the Mandelbrot computation on the point (x, y). It returns the number of iterations needed to discover that (x, y) is not in the set, or 255 if 255 or more iterations are required (this will be the case for all points in the set, and perhaps a few others). Using this function, you will produce gray-scale and color images of the Mandelbrot set.

Part 2: gray-scale image. To produce the gray-scale image of the Mandelbrot set, you would need to perform the Mandelbrot calculation at every point in the plane. You cannot plot an infinite number of points, so you will restrict attention to a particular rectangular region (read in as input), and plot a "sample" n-by-n grid of evenly spaced points from the continuum. Large values of n will produce higher resolution images, at the cost of more computation. Your program will read in the integer n from standard input. It will also read in the x and y coordinates of the lower left (xmin, ymin) and upper right (xmax, ymax) endpoints of the rectangular region of interest. The interesting part of the Mandelbrot set occurs in a 2.0-by-2.0 box centered at (-0.5, 0.0): the data in mand32.txt has n = 32, (xmin, ymin) = (-1.5, -1.0), and upper right (xmax, ymax) = (0.5, 1.0). The other data files zoom in on different regions.

PostScript primer. We now describe how to plot the points by writing a C program that outputs a PostScript program. The following PostScript program draws a box and plots five points.

%! 50 50 translate 0 0 512 512 rectstroke 0.000 setgray 10 100 200 200 rectfill 0.250 setgray 300 400 92 92 rectfill 0.500 setgray 200 400 80 80 rectfill 0.750 setgray 64 356 64 64 rectfill 0.900 setgray 310.2 245.1 50.9 181.8 rectfill showpage

To understand how it works, put this program into a text file called test.ps and type "gs test.ps" (to send the result to the screen) or "lpr test.ps" (to send the result to the printer). The program draws a box around the 512 x 512 PostScript drawing canvas using the routine rectstroke. Then it draws five solid rectangles using the routine rectfill: the routine takes four arguments (which precede the call): the x and y coordinates of the lower left rectangle endpoint, and the width and height of the rectangle. The gray-scale level is set by a routine setgray that takes one arguments between 0.0 (black) and 1.0 (white).

Back to Part 2. Your task is to write a C program that produces this PostScript program as output, except with different arguments for the setgray and rectfill routines (and many more calls on them). Your main challenge here will be to translate and scale the plane coordinates from the rectangle with endpoints (xmin, ymin) and (xmax, ymax) to the PostScript box with endpoints (0, 0) and (512, 512). Also, be sure to adjust the width and height of the rectangles so that the rectangles just touch without overlapping. Choose the gray-scale for a point according to the formula 1.0 - t/255.0, where t is the number of iterations in the Mandelbrot calculation for that point. This ensures that all points in the set are colored black. Points just outside the set will be colored in shades of gray. You should perform the Mandelbrot at the center of each grid-box, and use this value to determine the gray-scale level, i.e., at the circled points in the figure below.

When you run your C program, read the input from one of the data files, and redirect its output to a file with the command "a.out < mand4.txt > mandgray4.ps". The file mandgray4.ps now contains a PostScript program! To debug, first make certain that your C program produces a valid PostScript program exactly like the sample program, except with different calls to rectfill and setgray.

Part 3: color image. The third part of the assignment is to generate a color version of the Mandelbrot set. For each point, the Mandelbrot calculation returns a value between 0 and 255. Depending on this value, you will plot the point in a different color using the setrgbcolor routine. The routine takes three arguments between 0 and 1. Red, green, and blue are (1,0,0), (0,1,0), and (0,0,1), respectively. Black is (0,0,0); white is (1,1,1). For example, since magenta is a mixture of red and blue, the following line plots a square in a shade of magenta.

0.800 0.000 0.800 setrgbcolor 128 128 64 64 rectfill

The input files supply a table that gives the three setrgbcolor parameters for each possible iteration count between 0 and 255. If the Mandelbrot computation takes t iterations, then use line t from the table (start counting from 0) as the 3 arguments for setrgbcolor. To do this, define three 256-element arrays (or one 2-dimensional array) and initialize it by reading the table from standard input using scanf(). These values will occur after n, xmin, ymin, xmax, and ymax in the input file.

Submission. Submit the following files: readme, mandgray.c, and mandcolor.c.

Extra credit. There are limitless opportunities to avoid boredom here and earn extra credit. For example, create your own data files that zoom way in on other interesting parts of the set, near "edges" and sharp corners, and experiment with different color maps. Or experiment with different update formulae for r and s.