Due: &fractals-due; Summary: You will write procedures that create fractal images using numeric recursion with several image models. Purposes: To gain further experience with numeric recursion. To gain further experience with deep recursion. To make neat images. Expected Time: Two to three hours. Collaboration: We encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment. Submitting: Email your answer to &grader-email;. The title of your email should have the form &fractals-subject; and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message. Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

According to Benoit Mandelbrot (The Fractal Geometry of Nature, W.H. Freeman and Company, 1982), a fractal is a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole. When visualized, this self-similarity property gives rise to rather striking images. As the title of Mandelbrot's book suggests, such behavior occurs quite regularly in nature, from the formation of ice crystals, to plant structures, to the reproduction of algae. You can see many such examples (with a plethora of images) on the Wikipedia page on fractals.

A common fractal is the Sierpinksi carpet, which is constructed by removing portions of a square. (Other Sierpinski forms can be constructed by removing portions of other figures, such as triangles.) In particular, one can think of a square has being broken up into a three-by-three grid of smaller squares. If we remove the central square, such a figure might look like the following. There are then eight squares left. We can repeat the same process on each of those eight squares, yielding something like the following. With a few more recursive steps, we end up with an interesting carpet. How might we accomplish the construction of the Sierpinksi carpet in Scheme? We can use the GIMP tools to select the portions of the carpet, and then unselect the portions we remove. If we treat Sierpinski drawing as selecting the carpet, rather than drawing the carpet, we can then do all sorts of interesting things with the selection. We can, for example, fill it with a blend, rather than a single color. (selection-compute-pixels! image (lambda (col row) (rgb-new col 0 row))) We might also find it useful to stroke the selection, perhaps with multiple sizes of brushes in different colors. For example, the following is made by stroking the selection with (in sequence) a black "Circle (11)" brush, a grey "Circle (09)" brush, a light grey "Circle (07)" brush, and a white "Circle (03)" brush. So, how do we make the carpet? We can first select the entire image, and then unselect all the holes. A procedure to that uses this algorithm might begin something like the following. (define image-select-sierpinski-carpet! (lambda (image recursion-depth) (letrec ((unselect-holes! (lambda (n top left width height) (let ((w (/ width 3.0)) (h (/ height 3.0))) (when (and (>= w 1) (>= h 1)) (image-select-rectangle! image SUBTRACT (+ left w) (+ top h) w h) ...))))) (image-select-all! image) (unselect-holes! recursion-depth 0 0 (image-width image) (image-height image))))) We then need to fill in appropriate code to recurse (and to decide when it has recursed to the desired depth). Add that code.

The so-called Koch Star or snowflake is a straightforward, yet visually interesting fractal. It belongs to a family of fractals called Lindenmayer systems that are described via a series of recursive "modifications" or re-write rules. Before describing the technical aspects of what this means, it may be useful to gain a more intuitive understanding of the process. Beginning with an equilateral triangle (the base case), one recursively modifies each side of the triangle as follows: Divide the side into three equally-sized segments. Draw an equilateral triangle with the middle segment as its base, pointing outward from the original triangle. Delete the middle segment, which is the base of the triangle drawn in the previous step. This process is repeated (recursively) as many times as desired on each side of the two new segments. More generally, Lindenmayer re-write systems are described via four elements: An alphabet, which represents the set of variables that can be replaced. Computationally, these are the names of recursive operations. A set of constants, which represent fixed elements. Computationally, these are the non-recursive operations that are performed. An axiom, which represents the initial state of the system. Computationally, this is the body of the "husk" procedure. A set of production rules which represent the rewrites of alphabet elements. Computationally, these are the definitions of the recursive procedures. Since fractals are self-similar and, in theory, go on forever, there are no explicit base cases to determine when the recursion should stop. Instead, these must be grafted on in a computational implementation to avoid infinite repetition. The following is the Lindenmayer system for the Koch snowflake: Alphabet: F Constants: + - Axiom: F++F++F Production rule: F --> F-F++F-F This system is best implemented using the turtle model of drawing. In this system, the symbol "F" means "draw forward" a specified length, "+" means "turn right 60 degrees", and "-" means "turn left 60 degrees". Write a procedure (koch-snowflake! turtle recursion-depth initial-side-length) that implements the Koch-snowflake rewrite rules as given above. Your procedure should be an implementation of the axiom, which makes calls to a recursive procedure specified by the production rule. The recursion should proceed to a depth of recursion-depth and the initial distance for the "F" command should be initial-side-length. Note that with each recursive call, the side length will change.

(koch-snowflake! t 0 66)	(koch-snowflake! t 1 66)	(koch-snowflake! t 2 66)	(koch-snowflake! t 3 66)

Note: You may wish to write non-recursive helper procedures to implement the "+" and "-" commands, as well as a recursive helper procedure to implement the "F" command. In implementing the "F" rule, you only need to move the turtle forward when you've reached the base case (the specified depth). Otherwise, "F" represents a recursive call, and there is no need to explicitly move the turtle.

Of course, the basic Sierpinski carpet is quite regular and symmetrical. As you've noted, some artists worry about such symmetry and regularity in images. Can we add some visual interest? One possibility is to divide the square up into non-equal portions. In the following, we've used the basic Sierpinski technique of removing a middle portion, but have used different criteria for determining that portion. (In this case, the middle portion is 2/5 of the width and 1/2 of the height, centered vertically and 2/5th of the way across.) Using any techniques you deem appropriate, create an interesting pattern using a variant of the Koch star approach, the Sierpinski carpet approach, or a combination thereof.

We will judge your code on clarity, concision and correctness. We will judge the images that you produce on how compelling and clever the image you produce is.