Unformatted text preview:

Lecture 2: Fractals from Recursive Turtle Programsuse not vain repetitions... Matthew 6: 71. FractalsPictured in Figure 1 are four fractal curves. What makes these shapes different from most of the curves we encountered in the previous lecture is their amazing amount of fine detail. In fact, if we were to magnify a small region of a fractal curve, what we would typically see is the entire fractal in the large. In Lecture 1, we showed how to generate complex shapes like the rosette by applying iteration to repeat over and over again a simple sequence of turtle commands. Fractals, however, by their very nature cannot be generated simply by repeating even an arbitrarily complicated sequence of turtle commands. This observation is a consequence of the Looping Lemmas for Turtle Graphics.Sierpinski Triangle Fractal Swiss Flag Koch Snowflake C-CurveFigure 1: Four fractal curves.2. The Looping LemmasTwo of the simplest, most basic turtle programs are the iterative procedures in Table 1 for generating polygons and spirals. The looping lemmas assert that all iterative turtle programs, no matter how many turtle commands appear inside the loop, generate shapes with the same general symmetries as these basic programs. (There is one caveat here, that the iterating index is not used inside the loop; otherwise any turtle program can be simulated by iteration.)POLY (Length, Angle) SPIRAL (Length, Angle, Scalefactor)Repeat Forever Repeat ForeverFORWARD Length FORWARD LengthTURN Angle TURN AngleRESIZE ScalefactorTable 1: Basic procedures for generating polygons and spirals via iteration.Circle Looping LemmaAny procedure that is a repetition of the same collection of FORWARD and TURN commands has the structure of POLY(Length, Angle), whereAngle = Total Turtle Turning within the LoopLength = Distance from Turtle’s Initial Position to Turtle’s Final Position within the LoopThat is, the two programs have the same boundedness, closing, and symmetry. In particular, if Angle ≠ € 2πk for some integer k, then all the vertices generated by the same FORWARD command inside the loop lie on a common circle.Spiral Looping LemmaAny procedure that is a repetition of the same collection of FORWARD, TURN, and RESIZE commands has the structure of SPIRAL(Length, Angle, Scalefactor), whereAngle = Total Turtle Turning within the LoopLength = Distance from Turtle’s Initial Position to Turtle’s Final Position during the First Iteration of the LoopScalefactor = Total Turtle Scaling within the LoopThat is, the two programs have the same boundedness and symmetry. In particular, if Angle ≠ € 2πk for some integer k, and Scalefactor ≠ € ±1, then all the vertices generated by the same FORWARD command inside the loop lie on a common spiral.To prove the Circle Looping Lemma, follow the turtle through two iterations of the loop and observe that the initial turtle state undergoes exactly the same change as the turtle traversing two iterations of the POLY procedure (see Figure 2 below). Since we are iterating through exactly the same loop over and over again, the looping turtle must end up in exactly the same state as the turtle executing the POLY procedure after every iteration of the loop. This observation is the essence of the Circle Looping Lemma. The Spiral Looping Lemma can be proved in an exactly analogous manner.€ •€ PolyProcedure•€ LoopingProgram•€ LoopingProgramFigure 2: The turtle traversing through two iterations of a loop.2Examples: The WALK procedure and the accompanying turtle path (Figure 3, left) provide typical embodiments of the Circle Looping Lemma. Notice that vertices generated by the same FORWARD command inside the loop lie on a common circle. Similarly, the PENTARAL procedure and the accompanying turtle path (Figure 3, right) are embodiments of the Spiral Looping Lemma. Notice that in the PENTARAL curve vertices generated by the same FORWARD command inside the outer loop of the program lie on a common spiral.WALK PENTARALRepeat Forever Repeat ForeverFORWARD 1 Repeat 5 TimesTURN € π/ 3FORWARD 1FORWARD € 1 / 4TURN € 2π/ 5TURN € π/ 4TURN € π/10FORWARD € 1 / 3RESIZE 1.06TURN € −π/ 2FORWARD € 3 / 5TURN € π/ 6Figure 3: The turtle paths corresponding to the WALK procedure (left) and the PENTARAL procedure (right). Notice that corresponding vertices in the WALK curve lie on a common circle and that corresponding vertices in the PENTARAL curve lie on a common spiral.When the POLY procedure generates either a regular polygon or star, the vertices clearly lie on a common circle. But for angles A that are incommensurable with € 2π -- that is, for angles A for which there are no integers € m,n such that € m A = 2nπ -- the curve does not close and it is not so obvious that the vertices generated by the POLY procedure must necessarily lie on a circle. Yet, as we can see from Figure 4, even when € 2π/ A is not rational, the vertices do nevertheless seem to lie on a common circle. We shall now give a simple proof of this result based on standard arguments from Euclidean geometry.3Figure 4: The output of the POLY procedure for different input angles A. From left to right: a regular ten sided polygon (€ A =π/ 5), a seven pointed star (€ A = 6π/ 7), and a figure that never closes (€ A =π2 / 2). Notice that in each case, the vertices lie on a common circle.Proposition 1: The vertices generated by the procedure POLY(Length, Angle) lie on a common circle for any angle € A ≠ 2πk, for some integer k, and any length € L ≠ 0.Proof: Consider the circle generated by the first three vertices € D, E,F visited by the turtle while executing the POLY procedure (see Figure 5). We need to show that the next vertex G visited by the turtle lies on the same circle -- that is, we need to show that € x = CG = R, where R is the radius of the circle circumscribed about € ΔDEF and C is the center of this circle. But€ ΔCDE ≅ ΔCEF since by construction the lengths of the three corresponding sides are equal (SSS). Now€ A +β+α= A +α+α⇒β=αTherefore€ ΔCEF ≅ ΔCFG because these triangles agree in two sides and an included angle (SAS). Hence, since € ΔCEF is isosceles, € ΔCFG is also


View Full Document

Rice COMP 360 - Study Notes

Documents in this Course
Radiosity

Radiosity

42 pages

Radiosity

Radiosity

22 pages

Load more
Download Study Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?