CS 307: 4. Snow and Trees

Due: Wednesday, September 26, 2001

This exercise introduces several examples of fractal structures, that is, structures where the same pattern is repeated at smaller scales. For these problems, use the turtle graphics functions that you wrote for the last assignment.

1. A Sierpinski gasket is formed from an equilateral triangle with holes cut out of it in the following way. Lines are drawn connecting the midpoints of the sides of the triangle, forming a new equilateral triangle in the center; this triangle is cut out and removed, leaving three smaller triangles in the corners. The same treatment is applied to the smaller triangles, recursively.

   Write a function (sierpinski lng n) that draws a Sierpinski gasket with a triangle whose largest side is of length lng and which has a recursion depth of n. The gasket should be drawn from the current position and orientation of the turtle. Note that we do not want to draw the part that is cut out -- only the part that is left. When n = 0, sierpinski should draw an equilateral triangle; otherwise, it should draw nothing, but move to appropriate positions and call itself, three times. Demonstrate that your program can draw a Sierpinski gasket at an arbitrary angle. What is the area of the Sierpinski gasket as n approaches infinity?

2. An interesting geometric shape is the von Koch snowflake curve, defined as follows. The initial shape for a snowflake curve is an equilateral triangle, composed of three straight lines. A line can be replaced by four lines, each 1/3 the length of the original line, where the middle 1/3 of the line is replaced by two lines that extend outside the original line:

   replaced by:

   Write a program (snowflake lng n) that draws a snowflake curve with a side of length lng and a recursion depth of n, beginning at the existing location and orientation of the turtle. A snowflake with n = 0 would be an equilateral triangle.

   A relatively easy way to implement a program to draw the snowflake curve is to think in terms of the turtle walking along the outline and drawing as it moves. You could implement a function (snow-line lng n) that draws a straight line of length lng if n = 0, or calls itself recursively four times otherwise.

   

   Is the area of the snowflake curve bounded in the limit as n approaches infinity? What about the perimeter of the snowflake curve as n approaches infinity?

3. A binary tree drawing can be defined in the following way. A branch is drawn at a specified angle and length; then two smaller branches are drawn at the end of that branch, at the original angle plus and minus a branching angle, and with a length that is a multiple (less than 1) of the original length; stop the recursion when the branch length is less than 4.

   Write a function (draw-tree lng angle multiple) that draws a tree in this manner. angle should be in degrees. You may define auxiliary functions as desired. Try several parameter values to obtain different trees.

   A problem that is encountered in designing computer chips is how to get power to the various parts of the chip while keeping the power lines in a plane. One solution to this problem is to lay out power in a recursive H pattern in which smaller H's are drawn at the tips of each larger H. Use parameters of 90 degrees for angle and (sqrt 0.5) for multiple with your draw-tree function to see how this arrangement covers the plane.

1. Benoit B. Mandelbrot, The fractal geometry of nature.
2. Prusinkiewicz, P., and Lindenmayer, A. (1990). The Algorithmic Beauty of Plants. Springer.
3. http://www.dotellall.com/article/fractals-and-scales.html
4. http://archives.math.utk.edu/topics/fractals.html has lots of links.