Unformatted text preview:

Turtles and FractalsRon GoldmanDepartment of Computer ScienceRice UniversityFractalsSierpinski Triangle Fractal Swiss FlagKoch Snowflake C-CurveBasic Turtle ProgramsPOLY (Length, Angle)Repeat ForeverFORWARD (Length)TURN (Angle)SPIRAL (Length, Angle, Scalefactor)Repeat ForeverFORWARD (Length)TURN (Angle)RESIZE (Scalefactor)PropositionsPOLY Proposition The vertices generated by the POLY program lie on a circle.SPIRAL Proposition The vertices generated by the SPIRAL program lie on a spiral.Examples of POLY Procedures€ Angle =π/ 5 € Angle = 3π/ 7€ Angle =π2 / 2Proof of POLY Proposition•RRRLLLx = RααααβAACDEF••••€ GΔCDE ≅ ΔCEF (SSS)A +β+α= A +α+α⇒β=α€ ΔCEF ≅ ΔCFG (SAS)∴ x = RLooping LemmasCircle 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 Turning within the LoopLength = Total Distance traveled 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.Looping Lemmas (continued)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 Turning within the LoopLength = Total Distance traveled within the LoopScalefactor = Total 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 allthe vertices generated by the same FORWARD command inside the loop lie on acommon spiral.Looping Program and Polygon ProcedureLoopingPr ogram•PolygonProcedure••LoopingPr ogramSample Looping ProgramWALKRepeat ForeverFORWARD 1TURN € π/ 3FORWARD € 1/ 4TURN € π/ 4FORWARD € 1/ 3TURN € −π/ 2FORWARD € 3/5TURN € π/6Looping CurveMore Sample Looping ProgramPolySpiralRepeat 20Spin[€ 2π/20Scale[1.01Poly[5, € 2π/5]]]]StarSpiralRepeat 20Spin[€ 2π/20Scale[1.1Poly[5, € 4π/5]]]]Looping SpiralsPolySpiral StarSpiralRecursionProblem: How can we generate more interesting shapes from turtle programs?Solution: RecursionFractals: Recursion made visible.Motivation for FractalsRepresenting Natural Objects• Snowflakes, Mountains, Trees KDrawing Interesting PicturesExploring Novel MathematicsPerforming Data CompressionFractal Curves and Turtle ProgramsFractal Curves• Fractal curves usually cannot be represented by simple analytic expressions.• Fractal curves are generally defined by-- Recursive Procedures-- Iterated Transformations-- Infinite SeriesTurtle Programs• Recursion is used to express self-similarity.• Coordinates are irrelevant to shape.• Turtle programs are easily translated into fractal programs.Examples• Fractal Gaskets• Bump Fractals• Other Self-Similar FractalsSierpinski GasketSierpinski GasketMain Idea• Make a smaller Sierpinski gasket at one of the corners. • Then move to another corner and make another small Sierpinski gasket. • Then move to another corner and make another small Sierpinski gasket. • Then return the turtle to its initial position and heading. Recursive Turtle ProgramSierpinski(Level)If Level = 0, Draw a TriangleElse Repeat 3 TimesRESIZE 1/2Sierpinski(Level–1)RESIZE 2MOVE 1TURN € 2π/3More Fractal GasketsPentagonal Gasket Fractal Swiss Flag Rectangular GasketKoch CurveKoch BumpKoch CurveKoch CurveBasic Idea• Make a smaller Koch curve along the first edge of the bump. • Then move to the next edge and make another small Koch curve. • Then move to the next edge and make another small Koch curve. • Then move to the next edge and make another small Koch curve. Simpler Approach• Replace each straight line on the bump by a Koch curve.• Replace each FORWARD command by a recursive call.Koch CurveKoch Bump Koch(Level) If Level = 0, FORWARD 1ElseRESIZE 1/3 → RESIZE 1/3FORWARD 1 → Koch(Level-1)TURN 60→ TURN 60FORWARD 1 → Koch(Level-1)TURN −120→ TURN −120FORWARD 1 → Koch(Level-1)TURN 60 → TURN 60FORWARD 1 → Koch(Level-1)RESIZE 3 → RESIZE 3Universal Bump–Fractal ProgramBump Bump_Fractal(Level)If Level = 0, FORWARD 1ElseTURN A1TURN A1RESIZE € S1→ RESIZE € S1FORWARD 1 → Bump_Fractal€ (Level −1)TURN € A2→ TURN € A2RESIZE € S2→ RESIZE € S2FORWARD 1 → Bump_Fractal€ (Level −1) M MFORWARD 1 → Bump_Fractal€ (Level −1)RESIZE € Sn+1→ RESIZE € Sn+1TURN € An+1→ TURN € An+1Typical Bump Assumptions1. Turtle Final Orientation = Turtle Initial Orientation• Total Turning = 0 •€ Akk=1n+1∑ = 0 2. Turtle Returns to Initial Line• Total Y–Distance = 0•€ SkSin Ajj=1k∑        k=1n∑ = 03. Turtle Travels Distance=Size Along Initial Line• Total X–Distance = Size•€ SkCos Ajj=1k∑        k=1n∑ = 1C–CurveC-BumpC-CurveC–CurveBump C(Level) If Level = 0, FORWARD 1ElseTURN 45→ TURN 45RESIZE € 22→ RESIZE € 22FORWARD 1 →€ C Level −1( )TURN −90→ TURN −90FORWARD 1 →€ C Level −1( )TURN 45→ TURN 45RESIZE € 2→ RESIZE € 2More Bumps on BumpsAdditional Examples• Rectangular Bumps• Pentagonal Bumps• Space Filling CurvesAdditional Extensions• Scales and Angles can be selected randomly.• Each FORWARD command can be replaced by a different FRACTAL program.• Fractal programs can be connected with TURN and FORWARD transitions.More Self-Similar FractalsFractal Hangman Fractal Bush Fractal TreeMore Self-Similar FractalsFractal Star Fractal Flower Fractal


View Full Document

Rice COMP 360 - Lecture Notes

Documents in this Course
Radiosity

Radiosity

42 pages

Radiosity

Radiosity

22 pages

Load more
Download Lecture 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 Lecture 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 Lecture 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?