Assignment 8: 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:

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:

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.

Please include instructions for generating the image you wish to have evaluated. If you write a procedure, be sure to include a call to your procedure with specific parameters for generating the image. Unless it takes an exorbitantly long time (several minutes), you do not need to include the image itself. We will generate it by running your instructions.