Take-home assessment 6: fractals and other-self similar images

We explore fractals, images that are similar at different scales, as well as other images that can be built from numeric recursion. Along the way, we practice with numeric recursion.

Please download the starter code:

• fractals.scm

And turn in your completed file to Gradescope when you are done!

Background: Building Sierpinski triangles

Informally, fractals are images that appear similar at different scales. Although this assessment will primarily emphasize fractals made from simple shapes, there are also fractals that are much less regular. For example, the coastline of almost any country is considered a fractal because coastlines are similarly "jagged" at any scale.

We will explain the self-similarity of regular shapes using one of the most straightforward regular fractals, the Sierpinski Triangle. Here's how you might think of those triangles.

We'll start with a blue, equilateral, triangle with side-length 128.

(define triangle-128 (solid-equilateral-triangle 128 "blue"))

Let's build another triangle with half that side length. If you recall your geometry, this triangle will have 1/4 the area of the original triangle.

(define triangle-64 (solid-equilateral-triangle 64 "blue"))

We can get a similar triangle to the original one (but with a "hole" in the middle) by appropriately combining three of those triangles, two side by side and then one over them.

(above triangle-64 (beside triangle-64 triangle-64))

Of course, we could use a similar process to build each of those three blue triangles.

And each of those.

And each of those.

And so on.

And so forth.

If we do this process sufficiently many times (perhaps "arbitrarily many times"), we end up with a structure called the "Sierpinski Triangle". Sierpinski triangles have many surprising mathematical properties, none of which are relevant to us at this time. Instead, we will use Sierpinski triangles to make cool-looking drawings!

We will start by defining the intermediate results recursively. Here's one way. We'll call a triangle that's been broken up n times a "level-n fractal triangle".

• A level-0 fractal equilateral triangle with edge-length len is just an equilateral triangle of edge-length len.
• A level-n fractal equilateral triangle with edge-length len is built from three level-(n-1) fractal equilateral triangles, each with edge-length len/2. For example, a level-5 fractal equilateral triangle with side-length 128 is built from three level-4 equilateral triangles, each with side length 64.

You can turn that into a recursive procedure, can't you? Don't worry; you'll have a chance to do so in the exercises below.

Once we can build fractal triangles, we can start varying them. For example, rather than making each sub-triangle the same color, we might make one lighter and another darker. If we use the "standard" technique of adding 32 to each color component to make colors "lighter" and subtracting 32 to make them "darker", we might end up with something like the following for a level-4 gray triangle.

Here's another one that we've built by making the top triangle redder, the bottom-left triangle greener, and the bottom-right triangle bluer. (I think this has six levels of recursion.)

And one where we've turned each middle triangle into the base color. (We've done that by overlaying the recursive result on a larger triangle.)

It looks a bit different if we just overlay the first one on gray.

When we do enough recursion, it may not matter all that much whether or not the base case is a triangle. (Is that surprising or intuitive?) For example, here are a set of shapes using the (above shape (beside shape shape)) formula with a square as the base case.

Somewhere along the way, I think we said that these techniques might help us make compelling (or repelling?) images. Here's an experiment with using that last approach with seven shades of red and then overlaying them.

Required "tests" for drawing functions

In this assignment, we don't have a good way to test your code for correctness automatically! The starter code provides example invocations of your functions that you should check. However, in addition to these examples, you should provide two additional invocations of each function, demonstrating different behavior than what the given examples show. When writing these examples:

• Write your two additional examples below the given examples in the appropriate section.
• Give each example an appropriate description with the description function.
• Please ensure that your code runs to completion in a reasonable amount of time! In other words, don't give your examples inputs that will take the program longer than a few seconds to execute!

Part one: Fractal triangles

Problem 1a: fractal-triangle

Write a procedure, fractal-triangle, that makes the basic fractal triangle described above.

;;; (fractal-triangle side color n) -> image?
;;;   side : positive-real?
;;;   color : rgb?
;;;   n : non-negative integer
;;; Make a fractal triangle of the given side length using `color` as 
;;; the primary color.

Warning: Because shapes generally can't have fractional width or height, you may find that fractal-triangle produces triangles that are slightly bigger than expected. Such a result is acceptable. You'll notice all of our tests use a size that's a power of two to address such issues.

Problem 1b: rgb-fractal-triangle

Write a procedure, rgb-fractal-triangle, that makes a fractal triangle in which the top triangle is "redder" than the basic color, the lower-left triangle is "greener" than the basic color, and the lower-right triangle is "bluer" than the basic color.

;;; (rgb-fractal-triangle side color n) -> image?
;;;   side : positive-real?
;;;   color : rgb?
;;;   n : non-negative integer
;;; Make a fractal equilateral triangle of the given side length using
;;; `color` as the primary color.  In the recursive steps, the base
;;; color of the top triangle is `(rgb-redder color)`, the base color
;;; of the lower-left triangle is `(rgb-greener color)`, and the base
;;; color of the lower-right triangle is `(rgb-bluer color)`.  

Problem 1c: new-rgb-fractal-triangle

As you saw in our examples, once we start changing colors, it can be nice to "fill in" the center triangle with the original color. You will find it easiest to do so by overlaying the fractal triangle on a same-size triangle in the original color.

Write a procedure, (new-rgb-fractal-triangle side color n), that does just that.

;;; (new-rgb-fractal-triangle side color n) -> image?
;;;   side : positive-real?
;;;   color : rgb?
;;;   n : non-negative integer
;;; Make a fractal equilateral triangle of the given side length using
;;; `color` as the primary color.  In the recursive steps, the base
;;; color of the top triangle is `(rgb-redder color)`, the base color
;;; of the lower-left triangle is `(rgb-greener color)`, and the base
;;; color of the lower-right triangle is `(rgb-bluer color)`.  The base
;;; color of the central triangle should be `color`.  

Problem 1d: fractal-right-triangle

Write a procedure, (fractal-right-triangle width height color n), that builds a right triangle using the fractal approach.

;;; (fractal-right-triangle height width color n) -> image?
;;;   width : positive-real?
;;;   height : positive-real?
;;;   color : color?
;;;   n : non-negative integer
;;; Make a fractal right triangle using `color` as the primary color.

Part two: Fractal squares (carpets)

Just as we can think of triangles as being made up of four sub-triangles, and we can use that idea to make fractal triangles, we can break squares up into sub-squares and use those to make fractal squares. The most common approach is to make a three-by-three grid of squares, building all but the center square recursively. How do we combine them? We can make each row with beside and then stack the three rows with above. What about the middle square, which we normally leave "blank"? I find it easiest to specify a color to use for the center. Here are the first few stages.

No, the limit of this is not a "Sierpinski square". However, it is normally referred to as a Sierpinski carpet".

Problem 2a. carpet-a

Write a procedure, (carpet-a size color-x color-y n) that makes an image like those above.

;;; (carpet-a size color-x color-y n) -> image?
;;;   size : positive real?
;;;   color-x : color?
;;;   color-y : color?
;;;   n : non-negative integere
;;; Create a `size`-by-`size` image of the standard fractal carpet with
;;; `n` levels of recursion, using `color-x` as the "primary" color and
;;; `color-y` as the center color.  

Problem 2b. carpet-b

Of course, there's no reason we have to recurse on those particular eight squares. We could, for example, use only six. Here's one such pattern.

Here(and elsewhere, we are seeing some strange artifacts from our squares having non-integer edge lengths.)

Write a procedure, (carpet-b size color-x color-y n), that makes images like this latest set.

;;; (carpet-b size color-x color-y n) -> image?
;;;   size : positive real?
;;;   color-x : color?
;;;   color-y : color?
;;;   n : non-negative integer.
;;; Create a `size`-by-`size` image of a fractal carpet with `n` levels
;;; of recursion, using `color-x` as the "primary" color and `color-y`
;;; as the "secondary" color.  Our pattern looks something like this.
;;; 
;;;     X y X
;;;     y y X
;;;     X X X
;;; 
;;; where `X` means "recurse" and `y` means "square with `color-y`.

Problem 2c: carpet-c

Those big squares really stand out, don't they? But we can handle that. Instead of just making a rectangle of color-y, we can recurse in those squares, too, flipping the primary and secondary colors. Here are the first few versions with that model, using the same pattern as in carpet-b.

Write a procedure, (carpet-c size color-x color-y n), that makes images like the latest set.

;;; (carpet-c size color-x color-y n) -> image?
;;;   size : positive real?
;;;   color-x : color?
;;;   color-y : color?
;;;   n : non-negative integer.
;;; Create a `size`-by-`size` image of a fractal carpet with `n` levels
;;; of recursion, using `color-x` as the "primary" color and `color-y`
;;; as the "secondary" color.  Our pattern looks something like this.
;;; 
;;;     X Y X
;;;     Y Y X
;;;     X X X
;;; 
;;; where `X` means "recurse keeping colors as they are" and `Y` means
;;; "recurse swapping the two colors".

Problem 2d: carpet-d

d. Just as we can recurse on the secondary squares, we can choose not to recurse on some of the primary color squares. Here's an example with a somewhat different pattern. You can see if you can determine the pattern by inspection, or you can read the documentation.

Write a procedure, (carpet-d size color-x color-y n), that makes images like the latest set.

;;; (carpet-d size color-x color-y n) -> image?
;;;   size : positive real?
;;;   color-x : color?
;;;   color-y : color?
;;;   n : non-negative integer.
;;; Create a `size`-by-`size` image of a fractal carpet with `n` levels
;;; of recursion, using `color-x` as the "primary" color and `color-y`
;;; as the "secondary" color.  Our pattern looks something like this.
;;; 
;;;     X y X
;;;     x Y x
;;;     X y X
;;; 
;;; where `X` means "recurse keeping colors as they are", `Y` means
;;; "recurse swapping the two colors", `x` means "square in `color-x`"
;;; and `y` means "square in `color-y`".

Problem 2e: carpet

At this point, you may feel like you want to experiment with different patterns of carpet recursion. And you could do so by making slight changes to carpet-d. However, it's much better to extend our procedure to take the pattern of recursion as a parameter. For example, the "pattern" for carpet-d is "XyXxYxXyX".

Write a procedure, (carpet pattern size color-x color-y n), that generalizes carpet generation using patterns.

(Note: This procedure is only required for an E.)

;;; (carpet pattern size color-x color-y n) -> image?
;;;   pattern ; string? (length 9, composed only of x, X, y, and Y)
;;;   size : positive real?
;;;   color-x : color?
;;;   color-y : color?
;;;   n : non-negative integer.
;;; Create a `size`-by-`size` image of a fractal carpet with `n` levels
;;; of recursion, using `color-x` as the "primary" color and `color-y`
;;; as the "secondary" color.  
;;; 
;;; The pattern is given by the letters in pattern, where `X` means
;;; "recurse" keeping colors as they are", `Y` means "recurse swapping
;;; the two colors", `x` means "square in `color-x`" and `y` means
;;; "square in `color-y`".  
;;; 
;;; The positions of the letters correspond to the parts of the pattern
;;; 
;;;      0 1 2
;;;      3 4 5
;;;      6 7 8

Part three: Freestyle

Using variants of the fractal approaches from parts 1 and 2, along with anything else you consider useful, come up with a recursive procedure, (my-fractal size color n) that creates a self-similar (or otherwise numerically recursive) image using the starting size, color, and non-negative integer.

Include three invocations of my-fractal that demonstrate your fractal on a variety of inputs.

Grading rubric

Redo or above

Submissions that lack any of these characteristics will get an N.

• Displays a good faith attempt to complete every required part of the assignment.

Meets expectations or above

Submissions that lack any of these characteristics but have all the prior characteristics will get an R.

• Includes the specified file, fractals.scm.
• Includes an appropriate header on all submitted files that includes the course, author, etc.
• Correctness
  • Code runs without errors.
  • Core functions are present and correct (except for non-obvious corner cases, when present)
    • Part 1:
      • (fractal-triangle side color n)
      • (rgb-fractal-triangle side color n)
      • (new-rgb-fractal-triangle side color n)
      • (fractal-right-triangle width height n)
    • Part 2:
      • (carpet-a size color-x color-y n)
      • (carpet-b size color-x color-y n)
      • (carpet-c size color-x color-y n)
      • (carpet-d size color-x color-y n)
  • Each function has two additional invocations beyond what is provided in the starter code.
• Design
  • Documents and names all core procedures correctly.
  • Code generally follows style guidelines.
  • my-fractal involves explicit or implicit recursion other than from invoking procedures in parts 1–3.

Exemplary / Exceeds expectations

Submissions that lack any of these characteristics but have all the prior characteristics will get an M.

• Correctness
  • Implementation of all core functions is completely correct, even in non-obvious corner cases when present.
  • Each set of tests includes at least one edge case (e.g., an empty list, if appropriate).
  • Extra functions are present and completely correct:
    • Part 2, problem 2e: (carpet pattern size color-x color-y n)
• Design
  • Function documentation is complete and appropriately evocative of each function's behavior.
  • Code follows style guidelines completely, with at most three minor errors present.
  • Code is well-designed, avoiding repeated work through decomposition and appropriate language constructs.
  • my-fractal involves a basic shape other than triangles, squares, and rectangles.