Assignment 7: Producing Playful Polygons


Due: 10:30 p.m., Tuesday, 8 April 2014

Summary: In this assignment, you will use turtles to explore mechanisms for constructing images based on a variety of regular polygons and other regular figures. Our focus will be on using lists, iteration, anonymous procedures, and recursion as ways to work with the turtle model.

Purposes: To give you more experience with the turtle model. To give you more comfort with anonymous procedures. To explore the complexities possible from simple operations.

Collaboration: You may work alone or in a group of up to size three. You may not work anyone you worked with on either of the previous two homework assignments. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Submitting: Email your answer to . The title of your email should have the form CSC151-01 Assignment 7: Turtles 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.

Assignment

Problem 1: Drawing Polygons

Write a procedure, (turtle-polygon! turtle side-length sides), that uses a turtle to draw a regular polygon with the specified number of sides, with each side of the specified length.

Important: Your procedure must return the turtle to its original position and angle. Your procedure must not change the turtle's brush or color.

Hint: Use repeat. The turtle must turn a total of 360 degrees to return to its original angle.

For example,

(turtle-polygon! t 100 3)

(turtle-polygon! t 100 4)

(turtle-polygon! t 60 5)

(turtle-polygon! t 40 6)

Problem 2: Spinning Polygons

Write a procedure, (turtle-spin-polygon! turtle side-length sides angle copies), that draws the given number of copies of the specified polygon by calling your turtle-polygon! procedure, with the turtle turned an angle of angle between polygons.

Important: As in problem one, your procedure must return the turtle to its original position and orientation.

For example,

(turtle-spin-polygon! t 50 4 15 10)

(turtle-spin-polygon! t 50 4 20 5)

(turtle-spin-polygon! t 50 4 5 20)

(turtle-spin-polygon! t 50 4 -30 5)

Problem 3: A New Way to Draw Polygons

A potential deficiency of each of the prior two procedures is that multiple polygons are joined at a vertex. The problem is, of course, that our basic polygon procedure draws polygons starting at a particular point, rather than centered at a certain point.

Copy the following procedure to your definitions pane.

(define turtle-centered-polygon! 
  (lambda (turtle radius sides)
    (let ([interior-angle (/ (* 180 (- sides 2)) sides)])
      (turtle-up! turtle)
      (turtle-forward! turtle radius)
      (turtle-down! turtle)
      (turtle-turn! turtle (- 180 (/ interior-angle 2)))
      (turtle-polygon! turtle (* 2 radius (sin (/ pi sides))) sides)
      (turtle-turn! turtle (/ interior-angle 2))
      (turtle-up! turtle)
      (turtle-forward! turtle radius)
      (turtle-turn! turtle 180)
      (turtle-down! turtle))))    

Experiment with this procedure to learn what it does. (Hint: Note that this procedure assumes your turtle-polygon! draws the first side of the polygon before turning.)

a. Document this procedure using the six-P style of documentation.

b. Explain why each expression in the procedure's body is necessary to achieve the result that you see. That is, explain each step of the algorithm in English.

Hint: You may find it useful to comment out each expression using a semicolon, one at a time, to see how the result of leaving out that expression differs from the desired result.)

Problem 4: Spun Polygons, Revisited

Write a procedure, (turtle-spin-centered-polygon! turtle radius sides angle copies).

This procedure should be very similar to turtle-spin-polygon!, from above, except that it will call the turtle-centered-polygon! procedure from above instead of your turtle-polygon! procedure from Problem 1.

Problem 5: Fractal Paths, or There's More Than One Way to Get From Here to There

Some folks have noted that there are multiple paths from one point to another. Right now, turtle-forward! simply has the turtle go forward the appropriate distance, such as the following image, in which the turtle moves forward 100 units.

However, the turtle could arrive at the same point by using a different path. For example, the turtle might go forward 1/3 of the distance, turn left 60 degress, go forward 1/3 of the distance, turn right 120 degrees, go forward 1/3 of the distance, turn left 60 degrees, and go forward the remaining 1/3 of the distance, as we see in the following image.

We can implement that process as follows.

(define turtle-forward-alt!
  (lambda (turtle distance)
    (turtle-forward! turtle (/ distance 3))
    (turtle-turn! turtle -60)
    (turtle-forward! turtle (/ distance 3))
    (turtle-turn! turtle 120)
    (turtle-forward! turtle (/ distance 3))
    (turtle-turn! turtle -60)
    (turtle-forward! turtle (/ distance 3))))

But wait! If turtle-forward-alt! moves the turtle forward the appropriate distance, can't we use the same mechanism for each of those four forward steps?

(define turtle-forward-alt2!
  (lambda (turtle distance)
    (turtle-forward-alt! turtle (/ distance 3))
    (turtle-turn! turtle -60)
    (turtle-forward-alt! turtle (/ distance 3))
    (turtle-turn! turtle 120)
    (turtle-forward-alt! turtle (/ distance 3))
    (turtle-turn! turtle -60)
    (turtle-forward-alt! turtle (/ distance 3))))

Hmmm. We're starting to get an interesting image, aren't we? In fact, the image we see is related to a famous figure called the Koch Star or snowflake. It will get more snowflake-like if we do the same process again, this time using turtle-forward-alt2

However, there's a problem with our code. We've written two nearly identical procedures that differ only in what subprocedure they call (the first calls turtle-forward!, the second calls turtle-forward-alt2!. If we want to go another step, we'll need to write yet another nearly-identical procedure, this time one that calls >turtle-forward-alt2!.

Is there a better solution? Certainly. Whenever we find that we're writing nearly identical code, we try to find a way to write a common procedure. In this case, we can achieve that goal by adding an extra parameter, n, to the procedure and make the procedure recur on n. Let's call that procedure (turtle-forward-new! turtle distance n). When n is 0, it simply moves forward the given amount. When n is greater than 0, it uses the “forward, turn, forward, turn, forward, turn, forward” approach, using the same procedure to move forward, but with with n decreased by 1. That is, if we call (turtle-forward-new! turtle 90 2), that call will spawn four recursive calls to (turtle-forward-new! turtle 30 1). Each of those, in turn, will spawn four recursive calls to (turtle-forward-new! turtle 10 0). Each of those will simply call (turtle-forward! turtle 10).

For those of you who want a more formal description of this process, look at the appendices to this assignment.

a. Implement, but do not document, turtle-forward-new!.

b. Write a procedure, (turtle-fractal-centered-polygon! turtle radius sides n), that makes a polygon-like object, using turtle-forward-new! to draw the sides.

Problem 6: Alternating Fractals

Here are an interesting pair of paths.

Path A: Turn right 60 degrees, go forward half the distance, turn left 60 degrees, go forward half the distance, turn left 60 degrees, go forward half the distance, turn right 60 degrees.

Path B: Turn left 60 degrees, go forward half the distance, turn right 60 degrees, go forward half the distance, turn right 60 degrees, go forward half the distance, turn left 60 degrees.

Once again, we can take a fractal approach and, when moving forward, we can use one of the two paths, rather than just turtle-forward!.

Let's make it interesting though. For path A, let's make the first forward use path B, the second forward use path A, and the third forward use path B. Similarly, for path B, let's make the first forward use path A, the second forward use path B, and the third use path A.

What happens? For one level of recursion, We get something like the following. (We show the normal path A in grey and the recursive BAB in black.)

Without the grey, we see the figure we actually get.

With an additional level of recursion, we get the following image.

And with one more level, we get this image.

These mutually recursive procedures generate the path-based form of a figure called “Sierpinski's triangle”.

Implement the procedures (sierpinski-a! turtle distance n) and (sierpinski-b! turtle distance n), using the paths described above.

Problem 7: Creative Turtles

Write a program that systematically generates an interesting image composed of a series of polygons and/or fractals. In addition to using some (or all) of the ideas in problems 1 through 6, you should incorporate at least one additional element, such as changing the elements' positions, size, colors or brushes, or even changing the number of sides between different polygons.

Important Evaluation Criteria

We will judge your solutions on their correctness, their conciseness, and the cleverness. We will also judge your solution to problem 7 on its creativity.

Appendix: Formalizing Snowflake-like Fractals

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:

  • Divide the side into three equally-sized segments.
  • Draw an equilateral triangle with the middle segment as its base, pointing outward from the original triangle.
  • Delete the middle segment, which is the base of the triangle drawn in the previous step.

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:

  • An alphabet, which represents the set of variables that can be replaced. Computationally, these are the names of recursive operations.
  • A set of constants, which represent fixed elements. Computationally, these are the non-recursive operations that are performed.
  • An axiom, which represents the initial state of the system. Computationally, this is the body of the "husk" procedure.
  • A set of production rules which represent the rewrites of alphabet elements. Computationally, these are the definitions of the recursive procedures.

Since fractals are self-similar and, in theory, go on forever, there are no explicit base cases to determine when the recursion should stop. Instead, these must be grafted on in a computational implementation to avoid infinite repetition.

The following is the Lindenmayer system for the Koch snowflake:

  • Alphabet: F
  • Constants: + -
  • Axiom: F++F++F
  • Production rule: F --> F-F++F-F

This system is best implemented using the turtle 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".

Your procedure implements this system.

(koch-snowflake! t 0 66) (koch-snowflake! t 1 66) (koch-snowflake! t 2 66) (koch-snowflake! t 3 66)

Similarly, here is the Lindenmayer system for the Sierpinski triangle:

  • Alphabet: A, B
  • Constants: + -
  • Axiom: A
  • Production rules: A --> B-A-B, B --> A+B+A

Jerod Weinman

Copyright 2007-2014 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.

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License .