University of Virginia Computer Science
CS150: Computer Science, Fall 2005
|Problem Set 3: L-System Fractals||
Out: 9 September 2005
Due: Monday, 19 September 2005
Collaboration Policy - Read Carefully
For this problem set, you may work alone or with a partner of your choice but different from anyone you have worked with on PS1 or PS2. If you work with a partner, you and your partner should turn in one assignment with both of your names on it and both people must participate fully in all of the work. You should read the whole problem set yourself and think about the questions before beginning to work on them with your partner.
You may discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people except for materials from previous CS200 courses.
If you use resources other than the class materials, indicate what you used along with your answer.
|Reading: There is no additional SICP reading for this problem set. You may want to re-read Sections 2.1 and 2.2.|
|Download: Download ps3.zip
to your machine and unzip it into your home directory
This file contains:
|Unlike in Problem Set 1 and Problem Set 2, you are expected to be able to understand all the code provided for this problem set (and all future problem sets in this class unless specifically explained otherwise). This problem set requires less reading and introduces fewer new ideas than Problem Set 1 or 2, but expects you to write considerably more code. As always, we recommend you start early and take advantage of the staffed lab hours.|
In this problem set, you will explore a method of creating fractals known as the Lindenmayer system (or L-system). Aristid Lindemayer, a theoretical biologist at the University of Utrecht, developed the L-system in 1968 as a mathematical theory of plant development. In the late 1980s, he collaborated with Przemyslaw Prusinkiewicz, a computer scientist at the University of Regina, to explore computational properties of the L-system and developed many of the ideas on which this problem set is based.
The idea behind L-system fractals is that we can describe a curve as a list of lines and turns, and create new curves by rewriting old curves. Everything in an L-system curve is either a forward line (denoted by F), or a right turn (denoted by Ra where a is an angle in degrees clockwise). We can denote left turns by using negative angles.
We create fractals by recursively replacing all forward lines in a curve list with the original curve list. Lindemayer found that many objects in nature could be described using regularly repeating patterns. For example, the way some tree branches sprout from a trunch can be described using the pattern: F O(R30 F) F O(R-60 F) F. This is interpreted as: the trunk goes up one unit distance, a branch sprouts at an angle 30 degrees to the trunk and grows for one unit. The O means an offshoot — we draw the curve in the following parentheses, and then return to where we started before the offshoot. The trunk grows another unit and now another branch, this time at -60 degrees relative to the trunk grows for one units. Finally the trunk grows for one more unit. The branches continue to sprout in this manner as they get smaller and smaller, and eventually we reach the leaves.
We can describe this process using replacement rules:
Start: (F)Here are the commands this produces after two iterations:
Rule: F ::= (F O(R30 F) F O(R-60 F) F)
Iteration 0: (F)
Iteration 1: (F O(R30 F) F O(R-60 F) F)
Iteration 2: (F O(R30 F) F O(R-60 F) F O(R30 F O(R30 F) F O(R-60 F) F) F O(R30 F) F O(R-60 F) F O(R-60 F O(R30 F) F O(R-60 F) F) F O(R30 F) F O(R-60 F) F)
Here's what that looks like:
The Great Lambda Tree of Infinite Knowledge and Ultimate Power
Note that L-system command rewriting is similar to the replacement rules in a BNF grammar. The important difference is that with L-system rewriting, each iteration replaces all instances of F in the initial string instead of just picking one to replace.
We can divide the problem of producing an L-system fractal into two main parts:
Here is a BNF grammar for L-system commands:
- CommandSequence ::= ( CommandList )
- CommandList ::= Command CommandList
- CommandList ::=
- Command ::= F
- Command ::= RAngle
- Command ::= OCommandSequence
- Angle ::= Number
|Question 1: Show that (F O(R-60 F) F) is a string in the language defined by our BNF grammar. To do this, you should start with CommandSequence, and show a sequence of replacements that follow the grammar rules that produce the target string. You can use the rule numbers above to identify the rules.|
We need to find a way to turn strings in this grammar into objects we can manipulate in a Scheme program. We can do this by looking at the BNF grammar, and converting the non-terminals into Scheme objects.
;;; CommandSequence ::= ( CommandList ) (define make-lsystem-command list) ;;; We represent the different commands as pairs where the first item in the ;;; pair is a tag that indicates the type of command: 'f for forward, 'r for ;;; rotate and 'o for offshoot. We use quoted letters to make tags, which ;;; evaluate to the quoted letter. The tag 'f is short for (quote f). ;;; Command ::= F (define (make-forward-command) (cons 'f #f)) ;; No value, just use false. ;;; Command ::= RAngle (define (make-rotate-command angle) (cons 'r angle)) ;;; Command ::= OCommandSequence (define (make-offshoot-command commandsequence) (cons 'o commandsequence))
| Question 2: It will be useful to have procedures
that take L-system commands as parameters, and return information about
those commands. Define the following procedures in ps3.ss:
You will find the following procedures useful:
You should be able to make up similar test cases yourself to make sure the other procedures you defined work.
> (is-forward? (make-forward-command))
> (is-forward? (make-rotate-command 90))
> (get-angle (make-rotate-command 90))
> (get-angle (make-forward-command))
Yikes! Attempt to get-angle for a command that is not an angle command
Start: (F)To produce levels of the tree fractal, we need a procedure that takes a list of L-system commands and replaces each F command with the list of L-system commands given by the rule.
Rule: F ::= (F O(R30 F) F O(R-60 F) F)
So, for every command in the list:
For example, consider a simple L-System rewriting:
Start: (F)We want to get:
Rule: F ::= (F R30 F)
Iteration1: (F R30 F)but if we just replace F's with (F R30 F) lists, we would get:
Iteration2: (F R30 F R30 F R30 F)
Iteration1: ((F R30 F))The easiest way to fix this problem is to flatten the result. The code should look similar to many recursive list procedures you have seen (this code is provided in lsystem.ss):
Iteration2: ((F R30 F) R30 (F R30 F))
(define (flatten-commands ll) (if (null? ll) ll (if (is-lsystem-command? (car ll)) (cons (car ll) (flatten-commands (cdr ll))) (flat-append (car ll) (flatten-commands (cdr ll)))))) (define (flat-append lst ll) (if (null? lst) ll (cons (car lst) (flat-append (cdr lst) ll))))
| Question 3: Define a procedure rewrite-lcommands
in ps3.ss that takes a list of L-system commands as its first parameter. The second
parameter is a list of L-system commands that should replace every forward
command in the first list of commands in the result.
Here's the easy part:
Complete the definition of rewrite-lcommands.(define (rewrite-lcommands lcommands replacement) (flatten-commands (map ; Procedure to apply to each command lcommands)))
To make interesting L-system curves, we will need to apply rewrite-lcommands many times. We will leave that until the last question. Next, we will work on turning sequences of L-system commands into curves we can draw.
We will use a coordinate system from (0, 0) to (1, 1):
|(0.0, 1.0)||(1.0, 1.0)|
|(0.0, 0.0)||(1.0, 0.0)|
Points have x and y coordinates. To represent points we would like to define procedures make-point, x-of-point and y-of-point. Our pictures will be more interesting if points can have color too. So, we represent a colored point using a list of three values: x, y and color:
Note that we have defined points so we can have both colored points and colorless points that appear black.(define (make-point x y) (list x y)) (define (make-colored-point x y c) (list x y c)) (define (is-colored-point? (= (length point) 3) (define (x-of-point point) (car point)) (define (y-of-point point) (cadr point)) ;; (cadr x) = (car (cdr x)) ;;; Regular points are black. Colored points have a color. (define (color-of-point point) (if (is-colored-point? point) (caddr point) ;; == (car (cdr (cdr point))) (make-color 0 0 0)))
We have provided some procedures for drawing on the window in graphics.ss:
(define (mid-line t) (make-point t 0.5))defines a curve that is a horizontal line across the middle of the window. If we apply mid-line to a value x, we get the point (x, 0.5). Hence, if we apply mid-line to all values between 0.0 and 1.0, we get a horizontal line.
Predict what (x-of-point (mid-line 0.7)) and (y-of-point (mid-line 0.7)) should evaluate to. Try them in your Interactions window.
Of course, there are infinitely many values between 0.0 and 1.0, so we can't apply the curve function to all of them. Instead, we select enough values to show the curve well. To draw a curve, we need to apply the curve procedure to many values in the range from 0.0 to 1.0 and draw each point it evaluates to. Here's a procedure that does that:
(define (draw-curve-points curve n) (define (draw-curve-worker curve t step) (if (<= t 1.0) (begin (window-draw-point (curve t)) (draw-curve-worker curve (+ t step) step)))) (draw-curve-worker curve 0.0 (/ 1 n)))The procedure draw-curve-points takes a procedure representing a curve, and n, the number of points to draw. It calls the draw-curve-worker procedure. The draw-curve-worker procedure takes three parameters: a curve, the current time step values, and the difference between time step values. Hence, to start drawing the curve, draw-curve-points evaluates draw-curve-worked with parameters curve (to pass the same curve that was passed to draw-curve-points), 0.0 (to start at the first t value), and (/ 1 n) (to divide the time values into n steps).
The draw-curve-worker procedure is defined recursively: if t is less than or equal to 1.0, we draw the current point using (window-draw-point (curve t)) and draw the rest of the points by evaluating (draw-curve-worker curve (+ t step) step)).
The draw-curve-worker code uses the special form begin. The evaluation rule for begin is:
Evaluation Rule 4 - begin. To evaluate (begin Expression1 Expression2 ... Expressionk), evaluate each sub-expression in order from left to right. The value of the begin expression is the value of Expressionk.We stop once t is greater than 1.0, since we defined the curve over the interval [0.0, 1.0].
For example, the procedure rotate-ccw takes a curve and rotates it 90 degrees counter-clockwise by swapping the x and y points:
(define (rotate-ccw curve) (lambda (t) (let ((ct (curve t))) (make-colored-point (- (y-of-point ct)) (x-of-point ct) (color-of-point ct)))))We use let here to avoid needing to evaluate (curve t) more than once. In class, we will see that let is just syntactic sugar (that is, a short way of writing) a procedure application. It binds the value (curve t) evaluates to, to the name ct.
Note that (rotate-ccw c) evaluates to a curve. The function rotate-ccw is a procedure that takes a procedure (a curve) and returns a procedure that is a curve.
Predict what (draw-curve-points (rotate-ccw mid-line) 1000) and (draw-curve-points (rotate-ccw (rotate-ccw mid-line)) 1000) will do. Confirm your predictions by trying them in your Interactions window.
Here's another example:
(define (shrink curve scale) (lambda (t) (let ((ct (curve t))) (make-colored-point (* scale (x-of-point ct)) (* scale (y-of-point ct)) (color-of-point ct)))))Predict what (draw-curve-points (shrink mid-line .5) 1000) will do, and then try it in your Interactions window.
The shrink procedure doesn't produce quite what we want because in addition to changing the size of the curve, it moves it around. Why does this happen? Try shrinking a few different curves to make sure you understand why the curve moves.
One way to fix this problem is to center our curves around (0,0) and then translate them to the middle of the screen. We can do this by adding or subtracting constants to the points they produce:
(define (translate curve x y) (lambda (t) (let ((ct (curve t))) (make-colored-point (+ x (x-of-point ct)) (+ y (y-of-point ct)) (color-of-point ct)))))Now we have translate, it makes more sense to define mid-line this way:
(define (horiz-line t) (make-point t 0)) (define mid-line (translate horiz-line 0 0.5))
|Question 5: To check you understand everything so far, define a procedures draw-half-line that uses translate, horiz-line and shrink to draw a line half the width of the window that is centered in the middle of the display window.|
In addition to altering the points a curve produces, we can alter a curve by changing the t values it will see. For example,
(define (first-half curve) (lambda (t) (curve (/ t 2))))is a function that takes a curve and produces a new curve that is just the first half of the passed curve.
Predict what each of these expressions will do:
The provided code includes several other functions that transform
It is also useful to have curve transforms where curves may be combined. An example is (connect-rigidly curve1 curve2) which evaluates to a curve that consists of curve1 followed by curve2. The starting point of the new curve is the starting point of curve1 and the end point of curve2 is the ending point of the new curve. Here's how connect-rigidly is defined:
(define (connect-rigidly curve1 curve2) (lambda (t) (if (< t (/ 1 2)) (curve1 (* 2 t)) (curve2 (- (* 2 t) 1)))))Predict what (draw-curve-points (connect-rigidly vertical-mid-line mid-line) 1000) will do. Is there any difference between that and (draw-curve-points (connect-rigidly mid-line vertical-mid-line) 1000)? Check your predictions in the Interactions window.
The way connect-rigidly is defined above, we use all the t-values below 0.5 on the first curve, and use the t-values between 0.5 and 1.0 on the second curve. If the second curve is the result of connecting two other curves, like (connect-rigidly c1 (connect-rigidly c2 c3)) then 50% of the points will be used to draw c1, 25% to draw c2 and 25% to draw c3.
Question 6: Define a procedure num-points that determines the approximate
number of t-values that will be used for the
nth curve when drawing
(connect-rigidly c1 (connect-rigidly c2 (connect-rigidly curve3 (... cn))))Think about this yourself first, but look in ps3.ss for a hint if you are stuck. There are mathematical ways to calculate this efficiently, but the simplest way to calculate it is to define a procedure that keeps halving the number of points n times to find out how many are left for the nth curve.
Your num-points procedure should produce results similar to:
This means if we connected just 20 curves using connect-rigidly, and passed the result to draw-curve-points with one million as the number of points, there would still be only one or two points drawn for the 20th curve. If we are drawing thousands of curves, for most of them, not even a single point would be drawn!
> (exact->inexact (num-points 1000 10))
> (exact->inexact (num-points 1000 20))
> (exact->inexact (num-points 1000000 20))
To fix this, we need to distribute the t-values between our curves more fairly. We have provided a procedure connect-curves-evenly in graphics.ss that connects a list of curves in a way that distributes the range of t values evenly between the curves.
The definition is a bit complicated, so don't worry if you don't understand it completely. You should, however, be able to figure out the basic idea for how it distributed the t-values evenly between every curve in a list of curves.
It will also be useful to connect curves so that the next curve begins where the first curve ends. We can do this by translating the second curve to begin where the first curve ends. To do this for a list of curves, we translate each curve in the list the same way using map:(define (connect-curves-evenly curvelist) (lambda (t) (let ((which-curve (if (>= t 1.0) (- (length curvelist) 1) (inexact->exact (floor (* t (length curvelist))))))) ((get-nth curvelist which-curve) (* (length curvelist) (- t (* (/ 1 (length curvelist)) which-curve)))))))
(define (cons-to-curvelist curve curvelist) (let ((endpoint (curve 1.0))) ;; The last point in curve (cons curve (map (lambda (thiscurve) (translate thiscurve (x-of-point endpoint) (y-of-point endpoint))) curvelist))))
Here is the code for converting a list of L-System commands with some parts missing (it is explained below, but try to understand it yourself before reading further; if you don't understand cond, review SICP 1.1.6.):
(define (convert-lcommands-to-curvelist lcommands) (cond ((null? lcommands) (list ;;; We make a leaf with just a single point of green: (lambda (t) (make-colored-point 0.0 0.0 (make-color 0 255 0))) )) ((is-forward? (car lcommands)) (cons-to-curvelist vertical-line (convert-lcommands-to-curvelist (cdr lcommands)))) ((is-rotate? (car lcommands)) ;;; If this command is a rotate, every curve in the rest ;;; of the list should should be rotated by the rotate angle (let ;; L-system turns are clockwise, so we need to use - angle ((rotate-angle (- (get-angle (car lcommands))))) (map (lambda (curve) ;;; Question 7: fill this in ) ;;; Question 7: fill this in ))) ((is-offshoot? (car lcommands)) (append ;;; Question 8: fill this in )) (#t (error "Bad lcommand!"))))We define convert-lcommands-to-curvelist recursively. The base case is when there are no more commands (the lcommands parameter is null). It evaluates to the leaf curve (for now, we just make a point of green — you may want to replace this with something more interesting to make a better fractal). Since convert-lcommands-to-curvelist evaluates to a list of curves, we need to make a list of curves containing only one curve.
Otherwise, we need to do something different depending on what the first command in the command list is. If it is a forward command we draw a vertical line. The rest of the fractal is connected to the end of the vertical line using cons-to-curvelist. The recursive call to convert-lcommands-to-curve produces the curve list corresponding to the rest of the L-system commands. Note how we pass (cdr lcommands) in the recursive call to get the rest of the command list.
|Question 7: Fill in the missing code for handling rotate commands (marked as Question 7 in ps3.ss). You will want to use (rotate-around-origin curve rotate-angle) somewhere in your code to rotate every curve after the rotate command by the rotate-angle.|
You can test your code by drawing the curve that results from any list of L-system commands that does not use offshoots. For example, evaluating
should produce a "V".(draw-curve-points (position-curve (translate (connect-curves-evenly (convert-lcommands-to-curvelist (make-lsystem-command (make-rotate-command 150) (make-forward-command) (make-rotate-command -120) (make-forward-command)))) 0.3 0.7) 0 .5) 10000)
|Question 8: Fill in the missing code for handling offshoot commands (marked as Question 8 in ps3.ss).|
We have provided the position-curve procedure to make it easier to fit fractals onto the graphics window:
(position-curve curve startx starty) evaluates to a curve that translates curve to start at (startx, starty) and scales it to fit into the graphics window maintaining the aspect ratio (the x and y dimensions are both scaled the same amount)The code for position-curve is in curve.ss. You don't need to look at it, but should be able to understand it if you want to.
Now, you should be able to draw any l-system command list using position-curve and the convert-lcommands-to-curvelist function you completed in Questions 7 and 8. Try drawing a few simple L-system command lists before moving on to the next part.
| Question 9: Define a procedure make-lsystem-fractal
in ps3.ss that takes three parameters: replace-commands, a list of L-system
commands that replace forward commands in the rewriting; start,
a list of L-system commands that describes the starting curve; level,
the number of iterations to apply the rewrite rule.
Hint: You should use the rewrite-lcommands you defined in Question 3. You may also find it useful to use the n-times function from the September 12 class.
You should be able to draw a tree fractal using make-tree-fractal and draw-lsystem-fractal (these and the tree-commands list of L-system commands are defined in lsystem.ss):
(define (make-tree-fractal level) (make-lsystem-fractal tree-commands (make-lsystem-command (make-forward-command)) level))
(define (draw-lsystem-fractal lcommands) (draw-curve-points (position-curve (connect-curves-evenly (convert-lcommands-to-curvelist lcommands)) 0.5 0.1) 50000))
For example, (draw-lsystem-fractal (make-tree-fractal 3)) will create a tree fractal with 3 levels of branching.
|Question 10: Draw some fractals by playing with the L-system commands. Try changing the rewrite rule, the starting commands, level and leaf curve (in convert-lcommands-to-curvelist) to draw an interesting fractal. You might want to make the branches colorful also. Try an make a fractal picture that will make a better course logo than the current Great Lambda Tree Of Infinite Knowledge and Ultimate Power. The best pictures will appear on the course web page and will be rewarded with untold fame, invaluable fortune and maybe even a double gold star on this problem set. Turn in the code you used, as well as a printout of the display window. If your fractal deserves to be seen in color, email your code and an image of it to firstname.lastname@example.org.|
|Credits: This problem set was originally created for CS200 Spring 2002 by Dante Guanlao, Jon Erdman and David Evans, and revised for CS200 Spring 2003 by Jacques Fournier and David Evans, and revised for CS200 Spring 2004 and CS150 Fall 2005 by David Evans.|
|"); print ( $res[$first] ) ; print ("|
CS 150: Computer Science
University of Virginia
Using these Materials