CS212 Fall 1998Problem Set 1
Fractals
CS212 Fall 1998Before you do anything, please read about the entire assignment carefully. It contains a wealth of good advice that can save you (and us) a lot of headaches later on.
For this assignment, you are to work alone. Please turn in a copy of your code in class or in Upson 303 before 4pm. No late assignments will be accepted, so please start early.
If you have trouble with the course software or are generally stuck, come to our office hours or consulting hours. Alternatively, post a question to the newsgroup cornell.class.cs212 or email us at cs212@cs.cornell.edu.
In this problem set, you will be experimenting with fractals. Among the most famous fractals are the von Koch snowflake, first described by Helge von Koch in 1904, the Peano curve, the Hilbert curve, and the Cantor set. These figures not only look pretty, but also have some important applications. For example, the Hilbert curve is used in dithering and compressing images.
Many fractals can be specified by giving an initiator and a generator. The initiator is a starting shape, and the generator is a rule that can be applied to refine the shape. We can think of the initiator as a very rough initial approximation to the fractal. We can start with the initiator, then apply the generator as many times as we like to achieve better and better approximations. For the von Koch snowflake, the initiator is an equilateral triangle with sides oriented in a clockwise direction. (The red arrows show the direction of orientation only; they are not part of the figure.)
To generate the fractal corresponding to a given initiator and generator, we conceptually generate a sequence of figures, each figure more refined than the last. The first figure is the initiator. The i+1st figure is obtained by applying the generator to each oriented line segment in the ith figure. For the von Koch snowflake, the first figure would be the equilateral triangle, the second would be a six-pointed star, the third would be a six-pointed star with little bumps on each point, etc.
The fractal itself is the limit of these approximations. Fractals have a number of fascinating mathematical properties. They are self-similar, which means roughly that no matter how much you zoom in, the object still looks the same. They are continuous but nowhere differentiable. Their length is either 0 or infinite. One can define the dimension of a fractal in a natural way, and it turns out that their dimension is not 1 like curves or 2 like surfaces, but somewhere in between, which is why they are called fractals. The dimension of the von Koch snowflake is log 4/log 3 = 1.2618...
In this assignment you will construct level k approximations to fractals. These are the figures obtained by stopping the construction described above after stage k. For example, a level 0 von Koch snowflake consists of just an equilateral triangle; a level 1 von Koch snowflake is the six-pointed star; etc.
These figures can be created without having to actually generate the intermediate figures by using a recursive strategy for drawing a side of the figure. A level 0 side is just a straight line. A level k+1 side is made up of several level k sides. In the von Koch snowflake, a level k+1 side consists of four level k sides.
We can translate this strategy into a Dylan procedure that draws a side of a given level (specified by the parameter level) of a given length (specified by the parameter length) in a given direction (specified by the parameter heading), starting from the current position of the pen. If the level is 0, we simply draw a straight line of the given length in the given direction. If the level is greater than 0, we recursively draw four sides of level level-1 and length length/3 in the appropriate directions relative to the given direction.
(define (side <function>)
(method ((length <float>) (heading <float>) (level <integer>))
(if (= level 0)
(plot-line heading length)
(begin
(side (/ length 3) heading (- level 1))
(side (/ length 3) (- heading pi3) (- level 1))
(side (/ length 3) (+ heading pi3) (- level 1))
(side (/ length 3) heading (- level 1))))))
The procedure plot-line draws a line segment by moving a graphics "pen" in the specified direction for the specified distance.
We can draw the level k snowflake by drawing three level k sides oriented at 0 radians, 2pi/3 radians, and -2pi/3 radians, where pi = 3.14159...
(define (snowflake <function>)
(method ((length <float>) (level <integer>))
(side length 0.0 level)
(side length (* 2 pi3) level)
(side length (- 0.0 (* 2 pi3)) level)))
The file ps1.dyl contains two parts. The first part contains various graphics routines that you may find useful. This code uses some features of Dylan that you have not yet learned, so don't worry if you don't understand it. You will be writing similar code yourself in a few weeks. The second part consists of routines side and snowflake. This is the part you will be modifying.
Once you have loaded this code, you can test the program by evaluating the expression:
(snowflake 100.0 3)
to draw a level 3 snowflake of side-length 100. The length of the side must be explicitly written as 100.0, since NOODLLE will not convert an integer to a floating point number.
You may have a little trouble maneuvering the graphics window which pops up. Keep trying until you can get the entire image on your screen.
The snowflake figure is just one of a large family of figures that can be drawn using the same general method. Changing the generator and/or the initiator can completely change the shape of the figure.
Write a new generator method flip-side in which the first half of the oriented line segment is replaced with the two equal sides of an isoceles right triangle extending to the left and the last half with the two equal sides of an isoceles right triangle extending to the right.
Write a new initiator method square-snowflake that is a square instead of a triangle and uses flip-side as a generator. Try out your new initiator and see what kind of image it generates.
What to turn in: For problem 1, please submit a listing of the new methods flip-side and square-snowflake. Also print the snowflake generated by the following code:
(square-snowflake 100.0 3)
You can find the instructions on printing the contents of the Noodlle Graphics Console here.
Principle: Functional abstraction, functions as parameters.
In the initiator given to you and in the initiator you wrote, the shape of the generator is "hard-coded". But it makes perfect sense to define fractals using any combination of generator and initiator. For instance, we should be able to use the square initiator with the original von Koch generator. What we need is some general way to glue together a generator and initiator so that we can try out different combinations.
One idea is to parameterize the initiator by the generator. That is, we could modify initiators so that they take the generator as an argument.
Modify the definitions of snowflake and square-snowflake so that they take a generator as an argument and invoke this generator instead of a hardcoded one. Try out all four combinations of initiators and generators:
(snowflake 100.0 3 side) (snowflake 100.0 3 flip-side) (square-snowflake 100.0 3 side) (square-snowflake 100.0 3 flip-side)
In particular, evaluating the first expression should yield the same figure as the original snowflake code.
What to turn in: For problem 2, please submit a listing of the modified procedures snowflake and square-snowflake and a printout of all 4 generated snowflakes.
Principle: Functions as parameters.
There is no reason why the generators should stay the same all the time, even in the same figure. Interesting designs can be obtained by inverting the generator on some levels.
We can easily invert an arbitrary generator by changing the signs of the angles that we add to the original heading. The decision whether to use a regular or inverted generator could be a function of the level; for example, we might decide to invert the generator on odd levels and not to invert on even levels. Alternatively, we might decide to invert on every third level, or we might decide to never invert at all.
To support an arbitrary inversion strategy, we need to pass a procedure inverter to the initiator which then forwards inverter to the generator. The generator should call the inverter, passing in the current level, to determine the sign of the angle to add to the original heading. The inverter procedure should return either -1 or 1, telling whether to invert or not to invert, respectively.
Implement the changes indicated above by adding function inverter to the parameter list of snowflake and side. To test your code, evaluate:
(snowflake 100.0 3 side (method ((level <integer>)) 1))
and verify that you obtain the original snowflake figure as before.
What to turn in: For problem 3, please submit listings of the modified snowflake and side procedures and a printout of the snowflake, generated by the following code:
(snowflake 100.0 3 side (method ((level <integer>)) (if (odd? level) 1 -1)))
Principle: Functional programming vs. side effects.
Write two new procedures side-length and snowflake-length that take the same type of arguments as the procedures created in problem 3. However, instead of drawing anything, snowflake-length should return the total length of the figure that snowflake draws (i.e., the total distance moved by the pen), given the same arguments.
The overall structure of the two new procedures should be the same as the original, but each should return the length of the part of the figure that would have been drawn. It should be possible to do this with a fairly minimal change to the your solution to Problem 3. You do not need to write flip-side-length or square-snowflake-length.
What to turn in: For problem 4, please hand in a listing of the procedures side-length and snowflake-length and a printout of the output generated by the following code:
(snowflake-length 100.0 3 side-length (method ((level <integer>)) 1))
You probably generated some very interesting fractals in the course of this assignment. If you wish, you may select two of your best designs and enter them in the CS212 Awesome Fractal Contest. Submit the code which generates your fractal and a printout of the result. To be fair, please do not turn in more than two fractals. Designs will be judged by the CS212 staff. The winner will receive a prize.
For more about fractals and their mathematical properties, there is a short handout. See also Fractals: Form, Chance, and Dimension by Benoit B. Mandelbrot, Freeman, 1977.
CS212 home page