author Sam Moore Wed, 15 Jan 2014 12:29:12 +0000 (20:29 +0800) committer Sam Moore Wed, 15 Jan 2014 12:29:12 +0000 (20:29 +0800)
- Koch Snowflake (O(n^4)-ish !)

Reading Goldman's paper and hoping it will enlighten me.

 .gitignore patch | blob | history ipython_notebooks/fractals_basic.ipynb [new file with mode: 0644] patch | blob references/refs.bib patch | blob | history

index 0e36bc1..877fa0d 100644 (file)
@@ -10,3 +10,4 @@
*.test
nogit/*
references/*.pdf
+ipython_notebooks/.ipynb_checkpoints
diff --git a/ipython_notebooks/fractals_basic.ipynb b/ipython_notebooks/fractals_basic.ipynb
new file mode 100644 (file)
--- /dev/null
@@ -0,0 +1,318 @@
+{
+  "name": ""
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+  {
+   "cells": [
+    {
+     "level": 1,
+     "source": [
+      "Basic Fractals Stuff"
+     ]
+    },
+    {
+     "cell_type": "raw",
+     "source": [
+      "Main reference:\n",
+      "The Fractal Nature of Bezier Curves, Ron Goldman, Year?\n",
+      "\n",
+      "Also, wikipedia."
+     ]
+    },
+    {
+     "level": 2,
+     "source": [
+      "Definitions"
+     ]
+    },
+    {
+     "cell_type": "markdown",
+     "source": [
+      "Fractals are *attractors* Fixed points of *iterated function systems*. <cite data-cite=\"barnsley1993\"</cite>"
+     ]
+    },
+    {
+     "cell_type": "markdown",
+     "source": [
+      "An iterated function system: $W = \\left\\{w_1, ... w_n\\right\\}$ (collection of *maps* w_i)"
+     ]
+    },
+    {
+     "level": 2,
+     "source": [
+      "Stierpinski Triangle Generation"
+     ]
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "import random"
+     ],
+     "language": "python",
+     "outputs": [],
+     "prompt_number": 192
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "def stierpinski(n, x0 = (0,0)):\n",
+      "    \"\"\" Generates the Stierpinski Triangles using Iterated Function System \"\"\"\n",
+      "    # Define the maps in the iterated function system W\n",
+      "    W = [lambda p : (0.5*p[0], 0.5*p[1])] # scale\n",
+      "    W += [lambda p : (0.5*p[0]+0.25, 0.5*p[1] + 0.25*sqrt(3))] # scale & shift up&right\n",
+      "    W += [lambda p : (0.5*p[0]+0.5, 0.5*p[1])] # scale & shift right\n",
+      "    x = [x0]\n",
+      "    # Repeatedly randomly select one of the maps in W\n",
+      "    # As the number of iterations approaches infinity this becomes equivelant to the definition\n",
+      "    # (I think. I mean, it seems to work)\n",
+      "    for i in xrange(n):\n",
+      "        x.append(random.choice(W)(x[i]))\n",
+      "    return x\n",
+      "    "
+     ],
+     "language": "python",
+     "outputs": [],
+     "prompt_number": 193
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "points = stierpinski(10000, (0.5, 0.5))"
+     ],
+     "language": "python",
+     "outputs": [],
+     "prompt_number": 194
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "# Silly matplotlib needs x and y as seperate lists\n",
+      "x = [p[0] for p in points]\n",
+      "y = [p[1] for p in points]"
+     ],
+     "language": "python",
+     "outputs": [],
+     "prompt_number": 195
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "scatter(x, y, marker=',', s = 1e-3)"
+     ],
+     "language": "python",
+     "outputs": [
+      {
+       "output_type": "pyout",
+       "prompt_number": 196,
+       "text": [
+        "<matplotlib.collections.PathCollection at 0x79a6290>"
+       ]
+      },
+      {
+       "output_type": "display_data",
+       "text": [
+        "<matplotlib.figure.Figure at 0x7565150>"
+       ]
+      }
+     ],
+     "prompt_number": 196
+    },
+    {
+     "level": 2,
+     "source": [
+      "Koch Snowflake Generation"
+     ]
+    },
+    {
+     "cell_type": "markdown",
+     "source": [
+      "I worked this one out myself. You might say I'm a special *snowflake*."
+     ]
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "def koch1(n, x0 = (0,0), x1 = (1,0)):\n",
+      "    \"\"\" Recursively generates a Koch Curve between two points \"\"\"\n",
+      "    s = asarray([x1[0] - x0[0], x1[1] - x0[1]]) # Get displacement from x0 to x1\n",
+      "    # Calculate normal vector\n",
+      "    normal = asarray([-s[1], s[0]])\n",
+      "    normal = normal / sum(normal*normal)**0.5\n",
+      "    # Calculate the three points \n",
+      "    # (I *think* that in the definition these are the maps that form the iterated function system)\n",
+      "    a = asarray(x0) + s/3. # 1/3 from x0 to x1\n",
+      "    b = asarray(x0) + 2.*s/3. # 2/3 from x0 to x1\n",
+      "    c = asarray(x0) + 0.5*s + ((sum(s*s)**0.5)/3.)*normal # Form an equilateral triangle with a & b\n",
+      "    \n",
+      "    # Make first generation of points\n",
+      "    p = [x0, tuple(a), tuple(c), tuple(b), x1]\n",
+      "    \n",
+      "    if (n <= 1):\n",
+      "        return p\n",
+      "    \n",
+      "    result = []\n",
+      "    for i in xrange(len(p)-1):\n",
+      "        result +=  koch1(n-1, p[i], p[i+1])[:-1]\n",
+      "        \n",
+      "    return result + [p[-1]]\n",
+      "\n",
+      "def koch(n, p):\n",
+      "    \"\"\" Generate Koch Curves between every two points in p, including between the last and first \"\"\"\n",
+      "    result = []\n",
+      "    for i in xrange(len(p)-1):\n",
+      "        result += koch1(n, p[i], p[i+1])[:-1]\n",
+      "    return result + koch1(n, p[-1], p[0])"
+     ],
+     "language": "python",
+     "outputs": [],
+     "prompt_number": 351
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "# Plot some iterations of it.\n",
+      "for n in xrange(5):\n",
+      "    points = koch(n, [(0,0),(0.5, 0.75), (1,0)])\n",
+      "    x = [p[0] for p in points]\n",
+      "    y = [p[1] for p in points]\n",
+      "    plot(x, y, ',-')"
+     ],
+     "language": "python",
+     "outputs": [
+      {
+       "output_type": "display_data",
+       "text": [
+        "<matplotlib.figure.Figure at 0xdd3a110>"
+       ]
+      }
+     ],
+     "prompt_number": 373
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "# Plot performance\n",
+      "# Python doesn't have an actual (good) profiler because apparently we don't care about efficiency :P\n",
+      "# (It has profilers but they all just print to stdout and don't actually return values)\n",
+      "from time import time\n",
+      "\n",
+      "nAverages = 5\n",
+      "nMax = 10\n",
+      "\n",
+      "costs = []\n",
+      "stddevs = []\n",
+      "for n in xrange(nMax):\n",
+      "    cost = []\n",
+      "    for i in xrange(nAverages):\n",
+      "        t0 = time()\n",
+      "        koch(n, [(0,0),(0.5, 0.75), (1,0)])\n",
+      "        cost += [time() - t0]\n",
+      "    costs += [mean(cost)]\n",
+      "    stddevs += [var(cost)**0.5]\n",
+      "    \n",
+      "figure()\n",
+      "errorbar(range(nMax), costs, xerr=0, yerr=stddevs)\n",
+      "title(\"Avg Time (s) vs n\")\n",
+      "\n"
+     ],
+     "language": "python",
+     "outputs": [
+      {
+       "output_type": "pyout",
+       "prompt_number": 432,
+       "text": [
+        "<matplotlib.text.Text at 0x10cc01d0>"
+       ]
+      },
+      {
+       "output_type": "display_data",
+       "text": [
+        "<matplotlib.figure.Figure at 0xd431a50>"
+       ]
+      }
+     ],
+     "prompt_number": 432
+    },
+    {
+     "cell_type": "markdown",
+     "source": [
+      "So I worked it out, but I didn't work it out very efficiently.\n",
+      "It appears to be $O(n^4)$ :S"
+     ]
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [
+      "plot(range(nMax), costs)\n",
+      "for deg in xrange(4,5):\n",
+      "    fit = numpy.polynomial.polynomial.polyfit(range(nMax), costs, deg)\n",
+      "    plot(linspace(0, nMax), map(lambda x : sum([fit[i]*x**i for i in xrange(len(fit))]), linspace(0, nMax)))"
+     ],
+     "language": "python",
+     "outputs": [
+      {
+       "output_type": "display_data",
+       "text": [
+        "<matplotlib.figure.Figure at 0x108f00d0>"
+       ]
+      }
+     ],
+     "prompt_number": 433
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": [],
+     "language": "python",
+     "outputs": []
+    }
+   ],
+  }
+ ]
+}
\ No newline at end of file
index 296c4bd..7b82326 100644 (file)
@@ -9,3 +9,16 @@
year = "1985 - 1999"
}

+% The Fractal Nature of Bezier Curves