Conversion Algorithms:Recursive Turtle Programs to Iterated Function SystemsTurtle GeometryTurtle State• POSITION: € P = (x,y) location -- where the turtle is• DIRECTION: € v = (v1,v2) vector -- direction the turtle is facingTurtle Commands• FORWARD(D) -- change position, and draw a straight line of D turtle steps• MOVE(D) -- change position, but do not draw a straight line• TURN(A) -- rotate heading by A, but do not change position• RESIZE(S) -- alter step size by a factor of S , but do not change position or headingTurtle Programs• Finite sequence of FORWARD, MOVE, TURN, and RESIZE commands• Draws points and lines generated by the turtle’s pathConformal GeometryConformal Framework• Rectangular Coordinate System• One Point (Origin) and Two Orthogonal Unit Vectors (Axes)Conformal Commands• TRANSLATE(v) -- translates a point € P to the location € P +v• ROTATE(A,Q) -- rotates a point P (or a vector v) about the point Q by the angle A• SCALE(S,Q) -- scales the distance from a point P to the point Q by the factor S (scales the length of a vector v by the factor S)Conformal Programs• Finite sequence of TRANSLATE, ROTATE, AND SCALE commands• Creates lines by connecting pairs of points• Draws points and lines generated by the affine transformationsComparisonsTurtle Geometry Conformal GeometryLocal GlobalIntrinsic ExtrinsicLine Determined by Point and Vector Line Determined by Two PointsOrder Dependent Order IndependentNo Memory MemoryState Coordinate SystemFractal RepresentationsRecursive Turtle Program (RTP)• Base Case: Turtle Program(€ TB)• Recursion: € Turtle Commands(T1),Turtle Recursion MTurtle Commands(Tp),Turtle RecursionTurtle Commands(Tp+1)Iterated Affine Transformations (IAT)• € IAT = M1,K,Mp{ } -- Contractive Conformal Maps• C = Condensation Set -- Finite Collection of Points and Lines•€ F0= Conformal Geometry -- Finite Collection of Points and Lines• € Fn+1= IAT (Fn)∪C = M1(Fn)∪L∪ Mp(Fn)∪CObservations• Must permit IAT to have a CONDENSATION SET, otherwise there are recursive turtle programs that do not correspond to any IAT.• Must permit turtle to have a MOVE command, otherwise there are IATs that do not correspond to any recursive turtle program.• Turtle programs have only:• Move, Forward, Turn, and Resize commands with constant parameters• Recursive calls• For the same fractal:• number of recursive calls in turtle program = number of functions in IATIndependence from Base CaseIterated Affine Transformations (IAT) • Converges to a unique fractal independent of the initial set € F0.• Consequence of trivial fixed point theorem.Recursive Turtle Programs (RTP)• Converge to the same fractal independent of the path that the turtle traverses in the base case between its initial and final states.• Consequence of equivalence of RTP and IAT.Turtles and Conformal IAT’sTheorem 1: IAT → TurtleEvery fractal generated by an orientation preserving conformal IAT can be generated by a recursive turtle program whose initial and final states are identical both in the base case and in the recursion.Theorem 2: Turtle → IATEvery fractal generated by a converging recursive turtle program can be generated by an orientation preserving conformal IAT.Turtles Fractals and Turtle ProgramsTheorem 3: Turtle → TurtleEvery fractal generated by a converging turtle program can be generated by a recursive turtle program whose initial and final states are identical both in the base case and in the recursion.Theorem 4: Turtle → TurtleThe fractal generated by a converging turtle program is independent of the path that the turtle traverses in the base case between the initial and final states.Changing StateTurtle States € S1= (P1,v1) and € S2= (P2,v2)Observationsi. there is a sequence of four turtle commands Turn(A), Move(D), Turn(B), Resize(S)that maps the turtle from € S1 to € S2.ii. there is a sequence of three conformal transformations translation, rotation, and scaling that maps € S1 to € S2.Two Turtle States€ •€ P1€ v1€ •€ P2€ v2€ D€ A€ BKey Observation #1 Suppose€ S1, € S2 = turtle states€ T1 ,€ T2 = turtle programs that differ only by the initial states € S1, € S2 € G1,G2 = geometry generated by € T1,T2If M: € S1 → € S2 (oriented conformal affine transformation) Then € G2= M(G1)Key Observation #2Suppose€ S1 = initial turtle state€ T1 = turtle programP = sequence of Move, Turn, and Resize commands (Turtle Program)€ T2= € (P,T1) (Do P first, then do € T1)€ G1,G2 = geometry generated by € T1,T2IfP: € S1 → € S2M: € S1 → € S2 (oriented conformal affine transformation)Then € G2= M(G1)ExamplesShift, Spin, ScaleConvergent Turtle ProgramsTurtle Program• Base Case: Turtle Program(€ TB)• Recursion: € Turtle Commands(T1),Turtle Recursion(R1) MTurtle Commands(Tp),Turtle Recursion(Rp)Turtle Commands(Tp+1)Convergence Constraint• The initial and final states of the turtle in the recursion are the same as the initial and final states of the turtle in the base case. State Transformations•€ (Rk−1,Tk): Sk−1→ Sk(Turtle Program)•€ Mk: S0→ Sk(Affine Transformation)Recursive Turtle Program → IATTurtle Program• Base Case: Turtle Program(€ TB)• Recursion: € Turtle Commands(T1),Turtle Recursion MTurtle Commands(Tp),Turtle RecursionTurtle Commands(Tp+1)Preprocessing•€ GB= Geometry Drawn by Base Case € (TB)•€ GR= Geometry Drawn by Recursion without Recursive Calls € (T1LTp+1)Iterated Affine Transformation• € IAT = M1,K,Mp{ }• Condensation Set = € GRAnalysis of CorrespondenceTurtle Recursion (Key Observation 2)•€ T0= GB• € Tn+1= M1(Tn)∪L∪ Mp(Tn)∪GRPreprocessing•€ GB= Geometry Drawn by Base Case € (TB)•€ GR= Geometry Drawn by Recursion without Recursive Calls € (T1LTp+1)•€ Tk,Rk −1: Sk−1→ Sk(Turtle Program)•€ Mk: S0→ Sk(Affine Transformation)IAT Recursion•€ F0= GB• € Fn+1= M1(Fn)∪L∪ Mp(Fn)∪GRExplicit AlgorithmsProblem• Need an explicit algorithm for generating the matrices in the IAT from the turtle commands in the Recursive Turtle Program.Ron’s Algorithm (ExoCentric)• Matrix products are taken in order from left to right.• Needs to keep track of turtle’s state.• All transformations are rooted at the turtles current state.Tao’s Algorithm (TurtleCentric)• Matrix products are taken in reverse