CSC151.02 2010S Functional Problem Solving : Assignments
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment] [Quiz]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Quizzes] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.01 2010S (Weinman)] [CSC151 2009F (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Due: 10:00 a.m., Wednesday, 14 April 2010
Summary: You will write procedures that create fractal images using numeric recursion with several image models.
Purposes: To gain further experience with numeric recursion. To gain further experience with deep recursion. To make neat images.
Expected Time: Two to three hours.
Collaboration: We encourage you to work in groups of size three. You may, however, work alone or work in a group of size two or size four. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Submitting:
Email your answer to <rebelsky@grinnell.edu>
. The title of your email
should have the form CSC151.01 2010S Assignment 7: Fractals
and
should contain your answers to all parts of the assignment. Scheme code
should be in the body of the message.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
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 turtles 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
(
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 koch-snowflake!
turtle
n
side-length
)n
and the initial distance for the "draw
forward" command should be 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: In implementing your procedure, you only need to move the turtle (the "F" command) when you've reached the base case (the specified depth). Otherwise, "F" represents a recursive call, in which case no explicit forward movement needs to be done.
Another 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 with (in sequence) A black Circle (11) brush, a grey Circle (09) brush, a lightgrey Circle (07) brush, and a white Circle (03) brush.
So, how do we make the carpet? Let's focus on the holes. A procedure to make holes might begin something like the following.
(define sierpinski-carpet-holes (lambda (image n left top 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)) ...)))
We then need to fill in appropriate code to recurse (and to decide when it's done recursing). Add that code.
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.
We will judge your code on clarity, concision and correctness. We will judge the images that you produce on how compelling and clever the image you produce is.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment] [Quiz]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Quizzes] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.01 2010S (Weinman)] [CSC151 2009F (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-10 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.