{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# The Algorithmic Beauty of Plants\n", "\n", "This F# notebook contains implementations, examples, drawings, etc. of the Lindenmayer systems (L-systems) described in the book *The Algorithmic Beauty of Plants* by Przemyslaw Prusinkiewicz and Aristid Lindenmayer. [The book is officially available for free as a PDF.](http://algorithmicbotany.org/papers/#abop)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Dependencies" ] }, { "cell_type": "code", "execution_count": 521, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
Installed Packages
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "#r \"nuget: SkiaSharp\"\n", "\n", "open SkiaSharp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Utilities" ] }, { "cell_type": "code", "execution_count": 522, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [], "source": [ "/// Represents angles in degrees\n", "[] type degrees\n", "\n", "/// Represents angles in radians\n", "[] type radians\n", "\n", "/// Removes any units of measure from the given float\n", "let inline removeUnits (x: float<_>) = float x\n", "\n", "/// Converts the angle in degrees to radians\n", "let convertDegreesToRadians (degrees: float) =\n", " (degrees * System.Math.PI / 180.0) * 1.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Deterministic Context Free (DOL) System\n", "\n", "In Section 1.2 on pages 3-6, DOL-systems are described.\n", "\n", "**Definition**: Let $V$ denote an alphabet, $V^*$ the set of all words over $V$, and $V^+$ the set of all nonempty words over $V$. A *string OL-system* is an ordered triplet $G = \\langle V, \\omega, P \\rangle$ where $V$ is the *alphabet* of the system, $\\omega\\in V^+$ is a nonempty word called the *axiom* and $P\\subset V\\times V^*$ is a finite *set of productions*. A production $(a, \\chi)\\in P$ is written as $a \\to \\chi$. The letter $a$ and the word $\\chi$ are called the *predecessor* and the *successor* of this production, respectively. It is assumed that for any letter $a\\in V$, there is at least one word $\\chi\\in V^*$ such that $a\\to \\chi$. If no production is explicitly specified for a given predecessor $a\\in V$, the *identity production* $a \\to a$ is assumed to belong to the set of productions $P$. An OL-system is *deterministic* (noted *DOL-system*) if and only if for each $a\\in V$ there is exactly one $\\chi\\in V^*$ such that $a\\to V$." ] }, { "cell_type": "code", "execution_count": 523, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "language": "fsharp" } }, "outputs": [], "source": [ "type Production =\n", " { Predecessor: char\n", " Successor: string }\n", "\n", "let production predecessor successor =\n", " { Predecessor = predecessor\n", " Successor = successor }\n", "\n", "type DOLSystem =\n", " { Alphabet: char list\n", " Axiom: string\n", " Productions: Production list }\n", "\n", "let verifyDeterminism dol =\n", " let predecessors =\n", " dol.Productions\n", " |> List.map (fun p -> p.Predecessor)\n", " (List.length predecessors) = (predecessors |> List.distinct |> List.length)\n", "\n", "let rewriteCharacter productions character =\n", " match List.tryFind (fun p -> p.Predecessor = character) productions with\n", " | Some {Successor = sucessor} -> sucessor\n", " | None -> string character\n", "\n", "let rewriteWord productions (word: string) =\n", " let stringSequence = Seq.map (rewriteCharacter productions) word\n", " String.Join(\"\", stringSequence)\n", "\n", "let iterate n dol =\n", " List.fold (fun word _ -> rewriteWord dol.Productions word) dol.Axiom [1..n]\n", "\n", "let printIterations n dol =\n", " for i in [0..n] do\n", " printfn \"%s\" (iterate i dol)\n", "\n", "let testProduction character =\n", " match character with\n", " | 'b' -> \"ad\"\n", " | 'a' -> \"cb\"\n", " | 'd' -> \"b\"\n", " | 'c' -> \"a\"\n", " | x -> string x" ] }, { "cell_type": "code", "execution_count": 524, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [], "source": [ "let inline (=>) (predecessor: char) (successor: string) =\n", " production predecessor successor" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following DOL-system example is that found in (1.1). In the current implementation of `DOLSystem`, we cannot represent characters such as $a_r$ since we are restricted to an alphabet consisting only of characters. To do something like `a_r` would required extending alphabet entries to strings, which would require more complex modeling and logic than we currently have in place. So, for now, $a_l$ is `a`, $a_r$ is `b`, $b_l$ is `c`, and $b_r$ is `d`." ] }, { "cell_type": "code", "execution_count": 525, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b\n", "ad\n", "cbb\n", "aadad\n", "cbcbbcbb\n" ] } ], "source": [ "let dol =\n", " { Alphabet = ['a'; 'b'; 'c'; 'd']\n", " Axiom = \"b\"\n", " Productions =\n", " [ 'b' => \"ad\"\n", " 'a' => \"cb\"\n", " 'd' => \"b\"\n", " 'c' => \"a\" ] }\n", "\n", "printIterations 4 dol" ] }, { "cell_type": "code", "execution_count": 526, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "b\n", "ad\n", "cbb\n", "aadad\n", "cbcbbcbb\n" ] } ], "source": [ "let dol =\n", " { Alphabet = ['a'; 'b'; 'c'; 'd']\n", " Axiom = \"b\"\n", " Productions =\n", " [ 'b' => \"ad\"\n", " 'a' => \"cb\"\n", " 'd' => \"b\"\n", " 'c' => \"a\" ] }\n", "\n", "printIterations 4 dol" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can use `MathString` provided by .NET Interactive to display a $\\LaTeX$ string and reproduce the output in the book on page 5." ] }, { "cell_type": "code", "execution_count": 527, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/latex": [ "$$a_r\\newline a_lb_r\\newline b_la_ra_r\\newline a_la_lb_ra_lb_r\\newline b_la_rb_la_ra_rb_la_ra_r$$" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "[ for n in [0..4] ->\n", " (iterate n dol)\n", " .Replace(\"a\", \"a_l\")\n", " .Replace(\"b\", \"a_r\")\n", " .Replace(\"c\", \"b_l\")\n", " .Replace(\"d\", \"b_r\") ]\n", "|> (fun s -> String.Join(@\"\\newline \", s))\n", "|> MathString" ] }, { "cell_type": "code", "execution_count": 528, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "F-F-F-F\n", "F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F\n" ] } ], "source": [ "let quadraticKochIsland =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"F-F+F+FF-F-F+F\" ] }\n", "\n", "printIterations 1 quadraticKochIsland" ] }, { "cell_type": "code", "execution_count": 529, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [], "source": [ "type Coordinate =\n", " { X: float\n", " Y: float }\n", "\n", "type TurtleCommand =\n", " | ForwardWithPenDown\n", " | ForwardWithPenUp\n", " | RotateRight\n", " | RotateLeft\n", "\n", "type Turtle =\n", " { Coordinate: Coordinate\n", " Heading: float\n", " StepSize: float\n", " AngleIncrement: float }\n", "\n", "let defaultTurtle =\n", " { Coordinate = {X = 0.0; Y = 0.0}\n", " Heading = 90.0\n", " StepSize = 10.0\n", " AngleIncrement = 90.0 }\n", "\n", "let handleCommand state command =\n", " match command with\n", " | ForwardWithPenDown ->\n", " let nextX = state.Coordinate.X + state.StepSize * cos (state.Heading |> convertDegreesToRadians |> removeUnits)\n", " let nextY = state.Coordinate.Y + state.StepSize * sin (state.Heading |> convertDegreesToRadians |> removeUnits)\n", " { state with Coordinate = {X = nextX; Y = nextY} }\n", " | ForwardWithPenUp ->\n", " let nextX = state.Coordinate.X + state.StepSize * cos (state.Heading |> convertDegreesToRadians |> removeUnits)\n", " let nextY = state.Coordinate.Y + state.StepSize * sin (state.Heading |> convertDegreesToRadians |> removeUnits)\n", " { state with Coordinate = {X = nextX; Y = nextY} }\n", " | RotateRight ->\n", " { state with Heading = state.Heading - state.AngleIncrement }\n", " | RotateLeft ->\n", " { state with Heading = state.Heading + state.AngleIncrement }\n", "\n", "let drawTurtle (path: SKPath) command state =\n", " let newState = handleCommand state command\n", " match command with\n", " | ForwardWithPenDown ->\n", " path.LineTo(single newState.Coordinate.X, single newState.Coordinate.Y)\n", " newState\n", " | ForwardWithPenUp ->\n", " path.MoveTo(single newState.Coordinate.X, single newState.Coordinate.Y)\n", " newState\n", " | RotateRight ->\n", " newState\n", " | RotateLeft ->\n", " newState\n", "\n", "let calculateExtremeCoordinates initialTurtle commands =\n", " let handleState (turtle, minX, minY, maxX, maxY) command =\n", " let newTurtle = handleCommand turtle command\n", " (newTurtle,\n", " min minX newTurtle.Coordinate.X,\n", " min minY newTurtle.Coordinate.Y,\n", " max maxX newTurtle.Coordinate.X,\n", " max maxY newTurtle.Coordinate.Y)\n", " let (_, minX, minY, maxX, maxY) =\n", " let initialState = (initialTurtle,\n", " initialTurtle.Coordinate.X,\n", " initialTurtle.Coordinate.Y,\n", " initialTurtle.Coordinate.X,\n", " initialTurtle.Coordinate.Y)\n", " List.fold handleState initialState commands\n", " {| Minimum = {X = minX; Y = minY}; Maximum = {X = maxX; Y = maxY} |}\n", "\n", "let normalizeStepSize desiredWidth desiredHeight turtle commands =\n", " let extremeCoordinates = calculateExtremeCoordinates turtle commands\n", " let {Coordinate.X = minX; Y = minY} = extremeCoordinates.Minimum\n", " let {Coordinate.X = maxX; Y = maxY} = extremeCoordinates.Maximum\n", " let maxDimension = max (maxX - minX) (maxY - minY)\n", " let newStepSize = (max desiredWidth desiredHeight) * turtle.StepSize / maxDimension\n", " { turtle with StepSize = newStepSize }\n", "\n", "let width = 500.0\n", "let height = 500.0\n", "let margin = 10.0\n", "\n", "let drawSystem (canvas: SKCanvas) initialTurtle commands =\n", " let turtle = normalizeStepSize width height initialTurtle commands\n", " let extremeCoordinates = calculateExtremeCoordinates turtle commands\n", " let {Coordinate.X = minX; Y = minY} = extremeCoordinates.Minimum\n", " let {Coordinate.X = maxX; Y = maxY} = extremeCoordinates.Maximum\n", "\n", " let turtleColor = SKColors.Black\n", " use turtlePaint = new SKPaint(\n", " Style = SKPaintStyle.Stroke,\n", " Color = SKColors.Black,\n", " StrokeWidth = 1.5f,\n", " IsAntialias = true)\n", " use originPaint = new SKPaint(\n", " Style = SKPaintStyle.StrokeAndFill,\n", " Color = SKColors.LawnGreen,\n", " StrokeWidth = 10.0f,\n", " StrokeCap = SKStrokeCap.Round)\n", "\n", " canvas.Clear(SKColors.WhiteSmoke)\n", "\n", " // The SkiaSharp canvas coordinates are such that the origin (0, 0) is in the\n", " // top-left and x increases to the right and y increases downward.\n", " //\n", " // The turtle coordinates are standard coordinates such that the origin (0, 0)\n", " // is in the center and x increases to the right and y increases upward.\n", " //\n", " // Thus, we do three transformations:\n", "\n", " // 1. Translate the origin so that we can fit the entire system on\n", " // the final canvas\n", " canvas.Translate(single -minX, single maxY)\n", "\n", " // 2. Rotate the axis 180 degrees. This rotates\n", " // ┌-----> x\n", " // |\n", " // |\n", " // v\n", " // y\n", " //\n", " // to\n", " //\n", " // y\n", " // ^\n", " // |\n", " // |\n", " // x <-----┘\n", " canvas.RotateDegrees(180.0f)\n", "\n", " // 3. Flip accross the y-axis\n", " // y\n", " // ^\n", " // |\n", " // |\n", " // └-----> x\n", " canvas.Scale(-1.0f, 1.0f)\n", "\n", " // Draw the starting point of the turtle with a green semi-transparent circle\n", " canvas.DrawPoint(single turtle.Coordinate.X, single turtle.Coordinate.Y, originPaint)\n", "\n", " use path = new SKPath()\n", "\n", " // Move the turtle to the starting point without drawing a line\n", " path.MoveTo(single turtle.Coordinate.X, single turtle.Coordinate.Y)\n", "\n", " let mutable state = turtle\n", "\n", " // Draw every command, passing the new state to the next iteration\n", " for command in commands do\n", " state <- drawTurtle path command state\n", "\n", " // Draw the constructed path onto the canvas\n", " canvas.DrawPath(path, turtlePaint)" ] }, { "cell_type": "code", "execution_count": 530, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [], "source": [ "let convertTurtleStringToCommands (s: string) =\n", " [for c in s.Replace(\" \", String.Empty) ->\n", " match c with\n", " | 'F' -> ForwardWithPenDown\n", " | 'f' -> ForwardWithPenUp\n", " | '+' -> RotateLeft\n", " | '-' -> RotateRight\n", " | _ -> raise (System.Exception \"invalid turtle character\")]\n", "\n", "let drawTurtleSystem n initialTurtle dol : SKBitmap =\n", " let commands =\n", " dol\n", " |> iterate n\n", " |> convertTurtleStringToCommands\n", "\n", " // Create a bitmap of the desiered width and height plus margins\n", " let bitmap = new SKBitmap(int width + 2 * int margin, int height + 2 * int margin)\n", " \n", " // Create a canvas that we will draw to the bitmap with\n", " use canvas = new SKCanvas(bitmap)\n", "\n", " // Translate the canvas so that what we draw to is contained within the margins\n", " canvas.Translate(single margin, single margin)\n", " \n", " drawSystem canvas initialTurtle commands\n", " bitmap" ] }, { "cell_type": "code", "execution_count": 531, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "let originPaint = new SKPaint(\n", " Style = SKPaintStyle.StrokeAndFill,\n", " Color = SKColors.Black,\n", " StrokeWidth = 2.0f,\n", " StrokeCap = SKStrokeCap.Round,\n", " IsAntialias = true)\n", "let bitmap = new SKBitmap(100, 100)\n", "let canvas = new SKCanvas(bitmap)\n", "canvas.Clear(SKColors.WhiteSmoke)\n", "canvas.Translate(50.0f, 50.0f)\n", "canvas.RotateDegrees(180.0f)\n", "canvas.Scale(-1.0f, 1.0f)\n", "canvas.DrawPoint(25.0f, 25.f, originPaint)\n", "let path = new SKPath()\n", "path.MoveTo(0.0f, -2.5f)\n", "path.LineTo(5.0f, -2.5f)\n", "path.LineTo(0.0f, 7.5f)\n", "path.LineTo(-5.0f, -2.5f)\n", "path.LineTo(0.0f, -2.5f)\n", "canvas.DrawPath(path, originPaint)\n", "\n", "bitmap" ] }, { "cell_type": "code", "execution_count": 532, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.6 (a)\n", "\n", "drawTurtleSystem 1 defaultTurtle quadraticKochIsland" ] }, { "cell_type": "code", "execution_count": 533, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.6 (b)\n", "\n", "drawTurtleSystem 3 defaultTurtle quadraticKochIsland" ] }, { "cell_type": "code", "execution_count": 534, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.7 (a)\n", "let quadraticKochIsland =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"F+FF-FF-F-F+F+FF-F-F+F+FF+FF-F\" ] }\n", "\n", "drawTurtleSystem 2 defaultTurtle quadraticKochIsland" ] }, { "cell_type": "code", "execution_count": 535, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.7 (b)\n", "let quadraticSnowflakeCurve =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"-F\"\n", " Productions =\n", " [ 'F' => \"F+F-F-F+F\" ] }\n", "\n", "drawTurtleSystem 4 defaultTurtle quadraticSnowflakeCurve" ] }, { "cell_type": "code", "execution_count": 536, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.8\n", "let islandsAndLakes =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF\"\n", " 'f' => \"ffffff\" ] }\n", "\n", "drawTurtleSystem 2 defaultTurtle islandsAndLakes" ] }, { "cell_type": "code", "execution_count": 537, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.9 (a)\n", "let kochA =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"FF-F-F-F-F-F+F\" ] }\n", "\n", "drawTurtleSystem 4 defaultTurtle kochA" ] }, { "cell_type": "code", "execution_count": 538, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.9 (b)\n", "let kochB =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"FF-F-F-F-FF\" ] }\n", "\n", "drawTurtleSystem 5 defaultTurtle kochB" ] }, { "cell_type": "code", "execution_count": 539, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.9 (c)\n", "let kochC =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"FF-F+F-F-FF\" ] }\n", "\n", "drawTurtleSystem 3 defaultTurtle kochC" ] }, { "cell_type": "code", "execution_count": 540, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.9 (d)\n", "let kochD =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"FF-F--F-F\" ] }\n", "\n", "drawTurtleSystem 4 defaultTurtle kochD" ] }, { "cell_type": "code", "execution_count": 541, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.9 (e)\n", "let kochE =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"F-FF--F-F\" ] }\n", "\n", "drawTurtleSystem 5 defaultTurtle kochE" ] }, { "cell_type": "code", "execution_count": 542, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.9 (f)\n", "let kochF =\n", " { Alphabet = ['F'; 'f'; '+'; '-']\n", " Axiom = \"F-F-F-F\"\n", " Productions =\n", " [ 'F' => \"F-F+F-F-F\" ] }\n", "\n", "drawTurtleSystem 4 defaultTurtle kochF" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Edge rewriting" ] }, { "cell_type": "code", "execution_count": 543, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [], "source": [ "let drawEdgeRewritingSystem n initialTurtle fass =\n", " let s = iterate n fass\n", " let turtleSystem = { fass with Axiom = s.Replace('L', 'F').Replace('R', 'F') }\n", " drawTurtleSystem 0 initialTurtle turtleSystem" ] }, { "cell_type": "code", "execution_count": 544, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.10 (a)\n", "// dragon curve\n", "let dragonCurve =\n", " { Alphabet = ['L'; 'R'; '+'; '-']\n", " Axiom = \"L\"\n", " Productions =\n", " [ 'L' => \"L+R+\"\n", " 'R' => \"-L-R\" ] }\n", "\n", "drawEdgeRewritingSystem 10 defaultTurtle dragonCurve" ] }, { "cell_type": "code", "execution_count": 545, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.10 (b)\n", "// Sierpinski gasket\n", "let sierpinskiGasket =\n", " { Alphabet = ['L'; 'R'; '+'; '-']\n", " Axiom = \"R\"\n", " Productions =\n", " [ 'L' => \"R+L+R\"\n", " 'R' => \"L-R-L\" ] }\n", "\n", "drawEdgeRewritingSystem 6 {defaultTurtle with Heading = 0.0; AngleIncrement = 60.0} sierpinskiGasket" ] }, { "cell_type": "code", "execution_count": 546, "metadata": { "dotnet_interactive": { "language": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.11 (a)\n", "// hexagonal Gosper curve\n", "let hexagonalGosperCurve =\n", " { Alphabet = ['L'; 'R'; '+'; '-']\n", " Axiom = \"L\"\n", " Productions =\n", " [ 'L' => \"L+R++R-L--LL-R+\"\n", " 'R' => \"-L+RR++R+L--L-R\" ] }\n", "\n", "drawEdgeRewritingSystem 4 {defaultTurtle with AngleIncrement = 60.0} hexagonalGosperCurve" ] }, { "cell_type": "code", "execution_count": 547, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.11 (b)\n", "// quadratic Gospher curve or E-curve\n", "let quadraticGosperCurve =\n", " { Alphabet = ['L'; 'R'; '+'; '-']\n", " Axiom = \"-R\"\n", " Productions =\n", " [ 'L' => \"LL-R-R+L+L-R-RL+R+LLR-L+R+LL+R-LR-R-L+L+RR-\"\n", " 'R' => \"+LL-R-R+L+LR+L-RR-L-R+LRR-L-RL+L+R-R-L+L+RR\" ] }\n", "\n", "drawEdgeRewritingSystem 2 defaultTurtle quadraticGosperCurve" ] }, { "cell_type": "code", "execution_count": 548, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.13 (b)\n", "// 9x9 E-tour\n", "let nineByNineEtour =\n", " { Alphabet = ['L'; 'R'; '+'; '-']\n", " Axiom = \"-R\"\n", " Productions =\n", " [ 'L' => \"\"\n", " 'R' => \"-LL+R+R-L-LR-L+RR+L+R-LRR+L+RL-L-R+R+L-L-RR\" ] }\n", "\n", "drawEdgeRewritingSystem 3 defaultTurtle quadraticGosperCurve" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Node rewriting" ] }, { "cell_type": "code", "execution_count": 549, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [], "source": [ "let drawNodeRewritingSystem n initialTurtle fass =\n", " let s = iterate n fass\n", " let turtleSystem = { fass with Axiom = s.Replace(\"L\", \"\").Replace(\"R\", \"\") }\n", " drawTurtleSystem 0 initialTurtle turtleSystem" ] }, { "cell_type": "code", "execution_count": 550, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.16 (a)\n", "let threeByThreeMacrotile =\n", " { Alphabet = ['L'; 'R'; 'F'; '+'; '-']\n", " Axiom = \"-L\"\n", " Productions =\n", " [ 'L' => \"LF+RFR+FL-F-LFLFL-FRFR+\"\n", " 'R' => \"-LFLF+RFRFR+F+RF-LFL-FR\" ] }\n", "\n", "drawNodeRewritingSystem 3 defaultTurtle threeByThreeMacrotile" ] }, { "cell_type": "code", "execution_count": 551, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.16 (b)\n", "let fourByFourMacrotile =\n", " { Alphabet = ['L'; 'R'; 'F'; '+'; '-']\n", " Axiom = \"-L\"\n", " Productions =\n", " [ 'L' => \"LFLF+RFR+FLFL-FRF-LFL-FR+F+RF-LFL-FRFRFR+\"\n", " 'R' => \"-LFLFLF+RFR+FL-F-LF+RFR+FLF+RFRF-LFL-FRFR\" ] }\n", "\n", "drawNodeRewritingSystem 2 defaultTurtle fourByFourMacrotile" ] }, { "cell_type": "code", "execution_count": 552, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.17 (a)\n", "let threeByThreePeanoCurve =\n", " { Alphabet = ['L'; 'R'; 'F'; '+'; '-']\n", " Axiom = \"L\"\n", " Productions =\n", " [ 'L' => \"LFRFL-F-RFLFR+F+LFRFL\"\n", " 'R' => \"RFLFR+F+LFRFL-F-RFLFR\" ] }\n", "\n", "drawNodeRewritingSystem 2 defaultTurtle threeByThreePeanoCurve" ] }, { "cell_type": "code", "execution_count": 553, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Note: The book's productions, i.e., the replacement rules, for Figure 1.17(b)\n", "// are incorrect. For one, it leaves off the heading adjustment (alpha), which\n", "// should be 45 degrees. Secondly, the production for L is incorrect. It should\n", "// be what is below.\n", "//\n", "// It was a bit difficult figuring out what the correct rule should be, but one\n", "// way that helped was to reduce down to one iteration. There, one can see that\n", "// the turns are incorrect. Before the incorrect turn though, there is a similar\n", "// turn with the rule `F+R-F-L+F+R+`. From there, one can replace the incorrect\n", "// rule `L-R-F+F+` with `F+R-F-L+F+R+` and then reverse the `L` and `R` placements\n", "// to get `F+L-F-R+F+L+`\n", "//\n", "// |<--------->|\n", "// Book (incorrect): \"L+F+R-F-L+F+R-F-L-F-R+F+L-F-R-F-L+F+R-F-L-F-R-F-L+F+R+F+L+F+R-F-L+F+R+F+L-R-F+F+L+F+R-F-L+F+R-F-L\"\n", "// Here (correct): \"L+F+R-F-L+F+R-F-L-F-R+F+L-F-R-F-L+F+R-F-L-F-R-F-L+F+R+F+L+F+R-F-L+F+R+F+L-F-R+F+L+F+R-F-L+F+R-F-L\"\n", "\n", "// Figure 1.17 (b)\n", "let fiveByFivePeanoCurve =\n", " { Alphabet = ['L'; 'R'; 'F'; '+'; '-']\n", " Axiom = \"L\"\n", " Productions =\n", " [ 'L' => \"L+F+R-F-L+F+R-F-L-F-R+F+L-F-R-F-L+F+R-F-L-F-R-F-L+F+R+F+L+F+R-F-L+F+R+F+L-F-R+F+L+F+R-F-L+F+R-F-L\"\n", " 'R' => \"R-F-L+F+R-F-L+F+R+F+L-F-R+F+L+F+R-F-L+F+R+F+L+F+R-F-L-F-R-F-L+F+R-F-L-F-R+F+L-F-R-F-L+F+R-F-L+F+R\" ] }\n", "\n", "drawNodeRewritingSystem 2 {defaultTurtle with Heading = 45.0; AngleIncrement = 45.0} fiveByFivePeanoCurve" ] }, { "cell_type": "code", "execution_count": 554, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "drawNodeRewritingSystem 3 {defaultTurtle with Heading = 45.0; AngleIncrement = 45.0} fiveByFivePeanoCurve" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Branching structures" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Bracketed OL-systems" ] }, { "cell_type": "code", "execution_count": 555, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [], "source": [ "type Coordinate =\n", " { X: float\n", " Y: float }\n", "\n", "type TurtleCommand =\n", " | ForwardWithPenDown\n", " | ForwardWithPenUp\n", " | RotateRight\n", " | RotateLeft\n", " | Push\n", " | Pop\n", " | NoOperation\n", "\n", "type Turtle =\n", " { Coordinate: Coordinate\n", " Heading: float\n", " StepSize: float\n", " AngleIncrement: float }\n", "\n", "type TurtleStack = Stack of Turtle list\n", " with\n", "\n", " member this.Push turtle =\n", " let (Stack stack) = this\n", " Stack (turtle :: stack)\n", "\n", " member this.Pop (): (Turtle option) * TurtleStack =\n", " match this with\n", " | Stack [] -> (None, Stack [])\n", " | Stack (head :: tail) -> (Some head, Stack tail)\n", "\n", "let defaultTurtle =\n", " { Coordinate = {X = 0.0; Y = 0.0}\n", " Heading = 90.0\n", " StepSize = 10.0\n", " AngleIncrement = 90.0 }\n", "\n", "type State =\n", " { Turtle: Turtle \n", " Stack: TurtleStack } with\n", "\n", " member this.SetAngleIncrement angleIncrement =\n", " {this with Turtle = {this.Turtle with AngleIncrement = angleIncrement}}\n", "\n", "let defaultState =\n", " { Turtle = defaultTurtle \n", " Stack = Stack [] }\n", "\n", "let handleCommand {State.Turtle = turtle; Stack = stack} command =\n", " match command with\n", " | ForwardWithPenDown ->\n", " let nextX = turtle.Coordinate.X + turtle.StepSize * cos (turtle.Heading |> convertDegreesToRadians |> removeUnits)\n", " let nextY = turtle.Coordinate.Y + turtle.StepSize * sin (turtle.Heading |> convertDegreesToRadians |> removeUnits)\n", " { Turtle = {turtle with Coordinate = {X = nextX; Y = nextY}}\n", " Stack = stack }\n", " | ForwardWithPenUp ->\n", " let nextX = turtle.Coordinate.X + turtle.StepSize * cos (turtle.Heading |> convertDegreesToRadians |> removeUnits)\n", " let nextY = turtle.Coordinate.Y + turtle.StepSize * sin (turtle.Heading |> convertDegreesToRadians |> removeUnits)\n", " { Turtle = {turtle with Coordinate = {X = nextX; Y = nextY}}\n", " Stack = stack }\n", " | RotateRight ->\n", " { Turtle = {turtle with Heading = turtle.Heading - turtle.AngleIncrement}\n", " Stack = stack }\n", " | RotateLeft ->\n", " { Turtle = {turtle with Heading = turtle.Heading + turtle.AngleIncrement}\n", " Stack = stack }\n", " | Push ->\n", " { Turtle = turtle\n", " Stack = stack.Push turtle }\n", " | Pop ->\n", " match stack.Pop () with\n", " | Some poppedTurtle, stack -> { Turtle = poppedTurtle; Stack = stack }\n", " | None, stack -> { Turtle = turtle; Stack = stack }\n", " | NoOperation ->\n", " { Turtle = turtle; Stack = stack }\n", "\n", "let drawTurtle (path: SKPath) command state =\n", " let newState = handleCommand state command\n", " match command with\n", " | ForwardWithPenDown ->\n", " path.LineTo(single newState.Turtle.Coordinate.X, single newState.Turtle.Coordinate.Y)\n", " newState\n", " | ForwardWithPenUp ->\n", " path.MoveTo(single newState.Turtle.Coordinate.X, single newState.Turtle.Coordinate.Y)\n", " newState\n", " | RotateRight | RotateLeft | Push | NoOperation ->\n", " newState\n", " | Pop ->\n", " path.MoveTo(single newState.Turtle.Coordinate.X, single newState.Turtle.Coordinate.Y)\n", " newState\n", "\n", "let calculateExtremeCoordinates initialState commands =\n", " let handleState (turtle, minX, minY, maxX, maxY) command =\n", " let newState = handleCommand turtle command\n", " (newState,\n", " min minX newState.Turtle.Coordinate.X,\n", " min minY newState.Turtle.Coordinate.Y,\n", " max maxX newState.Turtle.Coordinate.X,\n", " max maxY newState.Turtle.Coordinate.Y)\n", " let (_, minX, minY, maxX, maxY) =\n", " let initialState = (initialState,\n", " initialState.Turtle.Coordinate.X,\n", " initialState.Turtle.Coordinate.Y,\n", " initialState.Turtle.Coordinate.X,\n", " initialState.Turtle.Coordinate.Y)\n", " List.fold handleState initialState commands\n", " {| Minimum = {X = minX; Y = minY}; Maximum = {X = maxX; Y = maxY} |}\n", "\n", "let normalizeStepSize desiredWidth desiredHeight state commands =\n", " let extremeCoordinates = calculateExtremeCoordinates state commands\n", " let {Coordinate.X = minX; Y = minY} = extremeCoordinates.Minimum\n", " let {Coordinate.X = maxX; Y = maxY} = extremeCoordinates.Maximum\n", " let maxDimension = max (maxX - minX) (maxY - minY)\n", " let newStepSize = (max desiredWidth desiredHeight) * state.Turtle.StepSize / maxDimension\n", " { state with Turtle = {state.Turtle with StepSize = newStepSize} }\n", "\n", "let width = 500.0\n", "let height = 500.0\n", "let margin = 10.0\n", "\n", "let drawSystem (canvas: SKCanvas) initialState commands =\n", " let state = normalizeStepSize width height initialState commands\n", " let extremeCoordinates = calculateExtremeCoordinates state commands\n", " let {Coordinate.X = minX; Y = minY} = extremeCoordinates.Minimum\n", " let {Coordinate.X = maxX; Y = maxY} = extremeCoordinates.Maximum\n", "\n", " let turtleColor = SKColors.Black\n", " use turtlePaint = new SKPaint(\n", " Style = SKPaintStyle.Stroke,\n", " Color = SKColors.Black,\n", " StrokeWidth = 1.0f,\n", " IsAntialias = true)\n", " use originPaint = new SKPaint(\n", " Style = SKPaintStyle.StrokeAndFill,\n", " Color = SKColors.LawnGreen,\n", " StrokeWidth = 10.0f,\n", " StrokeCap = SKStrokeCap.Round)\n", "\n", " canvas.Clear(SKColors.WhiteSmoke)\n", "\n", " // The SkiaSharp canvas coordinates are such that the origin (0, 0) is in the\n", " // top-left and x increases to the right and y increases downward.\n", " //\n", " // The turtle coordinates are standard coordinates such that the origin (0, 0)\n", " // is in the center and x increases to the right and y increases upward.\n", " //\n", " // Thus, we do three transformations:\n", "\n", " // 1. Translate the origin so that we can fit the entire system on\n", " // the final canvas\n", " canvas.Translate(single -minX, single maxY)\n", "\n", " // 2. Rotate the axis 180 degrees. This rotates\n", " // ┌-----> x\n", " // |\n", " // |\n", " // v\n", " // y\n", " //\n", " // to\n", " //\n", " // y\n", " // ^\n", " // |\n", " // |\n", " // x <-----┘\n", " canvas.RotateDegrees(180.0f)\n", "\n", " // 3. Flip accross the y-axis\n", " // y\n", " // ^\n", " // |\n", " // |\n", " // └-----> x\n", " canvas.Scale(-1.0f, 1.0f)\n", "\n", " // Draw the starting point of the turtle with a green semi-transparent circle\n", " canvas.DrawPoint(single state.Turtle.Coordinate.X, single state.Turtle.Coordinate.Y, originPaint)\n", "\n", " use path = new SKPath()\n", "\n", " // Move the turtle to the starting point without drawing a line\n", " path.MoveTo(single state.Turtle.Coordinate.X, single state.Turtle.Coordinate.Y)\n", "\n", " let mutable state = state\n", "\n", " // Draw every command, passing the new state to the next iteration\n", " for command in commands do\n", " state <- drawTurtle path command state\n", "\n", " // Draw the constructed path onto the canvas\n", " canvas.DrawPath(path, turtlePaint)\n", "\n", "let convertTurtleStringToCommands (s: string) =\n", " [for c in s.Replace(\" \", String.Empty) ->\n", " match c with\n", " | 'F' -> ForwardWithPenDown\n", " | 'f' -> ForwardWithPenUp\n", " | '+' -> RotateLeft\n", " | '-' -> RotateRight\n", " | '[' -> Push\n", " | ']' -> Pop\n", " | _ -> NoOperation ]//raise (System.Exception \"invalid turtle character\")]\n", "\n", "let drawTurtleSystem n initialTurtle dol : SKBitmap =\n", " let commands =\n", " dol\n", " |> iterate n\n", " |> convertTurtleStringToCommands\n", "\n", " // Create a bitmap of the desiered width and height plus margins\n", " let bitmap = new SKBitmap(int width + 2 * int margin, int height + 2 * int margin)\n", " \n", " // Create a canvas that we will draw to the bitmap with\n", " use canvas = new SKCanvas(bitmap)\n", "\n", " // Translate the canvas so that what we draw to is contained within the margins\n", " canvas.Translate(single margin, single margin)\n", " \n", " drawSystem canvas initialTurtle commands\n", " bitmap" ] }, { "cell_type": "code", "execution_count": 556, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.24 (a)\n", "let figure1_24_a =\n", " { Alphabet = ['F'; '+'; '-'; '['; ']']\n", " Axiom = \"F\"\n", " Productions =\n", " [ 'F' => \"F[+F]F[-F]F\" ] }\n", "\n", "drawTurtleSystem 5 (defaultState.SetAngleIncrement 25.7) figure1_24_a" ] }, { "cell_type": "code", "execution_count": 557, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.24 (b)\n", "let figure1_24_b =\n", " { Alphabet = ['F'; '+'; '-'; '['; ']']\n", " Axiom = \"F\"\n", " Productions =\n", " [ 'F' => \"F[+F]F[-F][F]\" ] }\n", "\n", "drawTurtleSystem 5 (defaultState.SetAngleIncrement 20.0) figure1_24_b" ] }, { "cell_type": "code", "execution_count": 558, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.24 (c)\n", "let figure1_24_c =\n", " { Alphabet = ['F'; '+'; '-'; '['; ']']\n", " Axiom = \"F\"\n", " Productions =\n", " [ 'F' => \"FF-[-F+F+F]+[+F-F-F]\" ] }\n", "\n", "drawTurtleSystem 4 (defaultState.SetAngleIncrement 22.5) figure1_24_c" ] }, { "cell_type": "code", "execution_count": 559, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.24 (d)\n", "let figure1_24_d =\n", " { Alphabet = ['F'; '+'; '-'; '['; ']'; 'X']\n", " Axiom = \"X\"\n", " Productions =\n", " [ 'X' => \"F[+X]F[-X]+X\"\n", " 'F' => \"FF\" ] }\n", "\n", "drawTurtleSystem 7 (defaultState.SetAngleIncrement 20.0) figure1_24_d" ] }, { "cell_type": "code", "execution_count": 560, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.24 (e)\n", "let figure1_24_e =\n", " { Alphabet = ['F'; '+'; '-'; '['; ']'; 'X']\n", " Axiom = \"X\"\n", " Productions =\n", " [ 'X' => \"F[+X][-X]FX\"\n", " 'F' => \"FF\" ] }\n", "\n", "drawTurtleSystem 7 (defaultState.SetAngleIncrement 25.7) figure1_24_e" ] }, { "cell_type": "code", "execution_count": 561, "metadata": { "dotnet_interactive": { "language": "fsharp" }, "polyglot_notebook": { "kernelName": "fsharp" } }, "outputs": [ { "data": { "text/html": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "// Figure 1.24 (f)\n", "let figure1_24_f =\n", " { Alphabet = ['F'; '+'; '-'; '['; ']'; 'X']\n", " Axiom = \"X\"\n", " Productions =\n", " [ 'X' => \"F-[[X]+X]+F[+FX]-X\"\n", " 'F' => \"FF\" ] }\n", "\n", "drawTurtleSystem 5 (defaultState.SetAngleIncrement 22.5) figure1_24_f" ] } ], "metadata": { "kernelspec": { "display_name": ".NET (C#)", "language": "C#", "name": ".net-csharp" }, "language_info": { "name": "polyglot-notebook" }, "polyglot_notebook": { "kernelInfo": { "defaultKernelName": "csharp", "items": [ { "aliases": [], "name": "csharp" }, { "aliases": [], "name": "fsharp" } ] } } }, "nbformat": 4, "nbformat_minor": 2 }