{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Arithmetization of Space-Filling Curves" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If the number $t \\in [0,1[$ is given with the basis four, i.e.\n", "\n", "\$$\n", " t = 0_4.q_1 q_2 q_3 q_4 \\ldots,\n", "\$$\n", "then the mapping $h(t)$ of the Hilbert curve can be written as\n", "\$$\n", " h(0_4.q_1 q_2 q_3 q_4 \\ldots) =\n", " H_{q_1} \\circ H_{q_2} \\circ H_{q_3} \\circ H_{q_4} \\circ \\cdots\n", " \\left( 0 \\atop 0 \\right)\n", "\$$\n", "with the operators\n", "\$$\n", " \\begin{array}{rclrcl}\n", " H_0 &:=& \\left( \\begin{array}{cc} \n", " 0 & \\frac{1}{2} \\\\ \n", " \\frac{1}{2} & 0 \\end{array} \\right) \\displaystyle\n", " \\left( x \\atop y \\right) \n", " &\n", " H_1 &:=& \\left( \\begin{array}{cc} \n", " \\frac{1}{2} & 0 \\\\ \n", " 0 & \\frac{1}{2} \\end{array} \\right) \\displaystyle\n", " \\left( x \\atop y \\right) + \\left( 0 \\atop \\frac{1}{2} \\right) \n", " &\n", " H_2 &:=& \\left( \\begin{array}{cc} \n", " \\frac{1}{2} & 0 \\\\ \n", " 0 & \\frac{1}{2} \\end{array} \\right) \\displaystyle\n", " \\left( x \\atop y \\right) + \\left( \\frac{1}{2} \\atop \\frac{1}{2} \\right)\n", " &\n", " H_3 &:=& \\left( \\begin{array}{cc} \n", " 0 & -\\frac{1}{2} \\\\ \n", " -\\frac{1}{2} & 0 \\end{array} \\right) \\displaystyle\n", " \\left( x \\atop y \\right) + \\left( 1 \\atop \\frac{1}{2} \\right). \n", " \\end{array}\n", "\$$" ] }, { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Exercise 1: Calculation of $h$ for (in)finite fractions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "alculate the values $h\\left(\\frac{1}{8}\\right)$ and $h\\left(\\frac{1}{3}\\right)$." ] }, { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Exercise 2: Arithmetization of the Peano Curve" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Derive an arithmetization of the Peano curve (see figure \\ref{fig:peano}a), analog to the arithmetization of the Hilbert curve. So we are looking for a representation like\n", "\n", "\$$\n", " p(0.q_1 q_2 q_3 q_4 \\ldots) =\n", " P_{q_1} \\circ P_{q_2} \\circ P_{q_3} \\circ P_{q_4} \\circ \\cdots\n", " \\left( 0 \\atop 0 \\right)\n", "\$$\n", "\n", "constructed on an appropriate basis and with appropriate operators\n", "$P_0$, $P_1$, $\\dots$\n", "\n", "Develop an algorithm that computes the Peano function $p(t)$. \n", "\n", "Use the Peano function to plot the approximating polygon of the Peano curve (with Python)." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# include plotting functionality\n", "import matplotlib.pyplot as plt\n", "from math import floor\n", "\n", "def plotLineUp(x, y, length):\n", "\tx.append(x[len(x) - 1])\n", "\ty.append(y[len(y) - 1] + length)\n", " \n", "def plotCurveDelayed(x, y, delay):\n", "\tpx = []\n", "\tpy = []\n", "\tfig, ax = plt.subplots()\n", "\tax.set_xlim(min(x)-0.05, max(x)+0.05)\n", "\tax.set_ylim(min(y)-0.05, max(y)+0.05)\n", "\tfor i in xrange (len(x)):\n", "\t\tpx.append(x[i])\n", "\t\tpy.append(y[i])\n", "\t\tif i == 0:\n", "\t\t\tpoints, = ax.plot(px, py)\n", "\t\telse:\n", "\t\t\tpoints.set_data(px, py)\n", "\t\tplt.pause(delay)\n", "\t\t\n", " \tplt.show()\n", "\t\t\n", "\n", "def plotLineStrip(x, y, title = None):\n", "\tfig, ax = plt.subplots()\n", "\tplt.plot(x, y)\n", "\tif title is not None:\n", "\t\tplt.title(title)\n", "\tax.set_xlim(min(x)-0.05, max(x)+0.05)\n", "\tax.set_ylim(min(y)-0.05, max(y)+0.05)\n", "\tplt.show()\n" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [ "# arithmetization of the Hilbert curve\n", "def H0(pos):\n", "\tx = pos[1] * 0.5\n", "\ty = pos[0] * 0.5\n", "\treturn (x, y)\n", "\n", "def H1(pos):\n", "\tx = pos[0] * 0.5\n", "\ty = pos[1] * 0.5 + 0.5\n", "\treturn (x, y)\n", "\n", "def H2(pos):\n", "\tx = pos[0] * 0.5 + 0.5\n", "\ty = pos[1] * 0.5 + 0.5\n", "\treturn (x, y)\n", "\n", "def H3(pos):\n", "\tx = -pos[1] * 0.5 + 1.0\n", "\ty = -pos[0] * 0.5 + 0.5\n", "\treturn (x, y)\n" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 5 }, { "cell_type": "code", "collapsed": false, "input": [ "# arithmetization of the Peano curve\n", "def P0(pos):\n", "\t#TODO\n", "\n", "def P1(pos):\n", "\t#TODO\n", "\n", "def P2(pos):\n", "\t#TODO\n", "\n", "def P3(pos):\n", "\t#TODO\n", "\n", "def P4(pos):\n", "\t#TODO\n", "\n", "def P5(pos):\n", "\t#TODO\n", "\n", "def P6(pos):\n", "\t#TODO\n", "\n", "def P7(pos):\n", "\t#TODO\n", "\n", "def P8(pos):\n", "\t#TODO\n" ], "language": "python", "metadata": {}, "outputs": [ { "ename": "IndentationError", "evalue": "expected an indented block (, line 5)", "output_type": "pyerr", "traceback": [ "\u001b[0;36m File \u001b[0;32m\"\"\u001b[0;36m, line \u001b[0;32m5\u001b[0m\n\u001b[0;31m def P1(pos):\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m expected an indented block\n" ] } ], "prompt_number": 6 }, { "cell_type": "code", "collapsed": false, "input": [ "# arithmetization of the meander-type Peano curve\n", "def M0(pos):\n", "\t#TODO\n", "\n", "def M1(pos):\n", "\t#TODO\n", "\n", "def M2(pos):\n", "\t#TODO\n", "\n", "def M3(pos):\n", "\t#TODO\n", "\t\n", "def M4(pos):\n", "\t#TODO\n", "\n", "def M5(pos):\n", "\t#TODO\n", "\n", "def M6(pos):\n", "\t#TODO\n", "\n", "def M7(pos):\n", "\t#TODO\n", "\n", "def M8(pos):\n", "\t#TODO\n" ], "language": "python", "metadata": {}, "outputs": [ { "ename": "IndentationError", "evalue": "expected an indented block (, line 5)", "output_type": "pyerr", "traceback": [ "\u001b[0;36m File \u001b[0;32m\"\"\u001b[0;36m, line \u001b[0;32m5\u001b[0m\n\u001b[0;31m def M1(pos):\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m expected an indented block\n" ] } ], "prompt_number": 7 }, { "cell_type": "code", "collapsed": false, "input": [ "# set the number of the program you want to test\n", "prog = 2\n", "delay = 0.5\n", "\n", "depth = 1\n", "t_start = 0.0\n", "t_end = 1.0\n", "x = []\n", "y = []\n", "\n", "# plot approximatin polygon for the hilbert curve\n", "if prog == 1:\n", " print \"t_start:\", t_start, \" t_end:\", t_end\n", " while t_start < t_end:\n", "\t\thilbert = []\n", "\t\tpos = (0.0, 0.0)\n", "\t\ttemp = t_start\n", "\t\tfor i in xrange(depth):\n", "\t\t\tq = floor(4 * temp)\n", "\t\t\ttemp = 4 * temp - q\n", "\t\t\thilbert.append(q)\n", "\t\tfor i in xrange(len(hilbert)):\n", "\t\t\tif hilbert[len(hilbert)-i-1] == 0:\n", "\t\t\t\tpos = H0(pos)\n", "\t\t\telif hilbert[len(hilbert)-i-1] == 1:\n", "\t\t\t\tpos = H1(pos)\n", "\t\t\telif hilbert[len(hilbert)-i-1] == 2:\n", "\t\t\t\tpos = H2(pos)\n", "\t\t\telif hilbert[len(hilbert)-i-1] == 3:\n", "\t\t\t\tpos = H3(pos)\n", "\t\tprint t_start, \" -> \", pos[0], pos[1]\n", "\t\tx.append(pos[0])\n", "\t\ty.append(pos[1])\n", "\t\tt_start = t_start + 0.25**depth\n", "\n", "\t# x += [0, 0, 1, 1, 0]\n", "\t# y += [0, 1, 1, 0, 0]\n", " print 'x = ' + str(x)\n", " print 'y = ' + str(y)\n", " if delay > 0.0:\n", "\t\tplotCurveDelayed( x, y, delay)\n", "\telse:\n", "\t\tplotLineStrip(x, y, None)\n", "\t# plotLineStrip( (0,1), (0,0), None )\n", "\t# plotLineStrip( (0,0), (0,1), None )\n", "\t# plotLineStrip( (0,1), (1,1), None )\n", "\t# plotLineStrip( (1,1), (0,1), None )\n", "\t# plot approximatin polygon for a peano curve\n", "elif prog == 2:\n", "\teps = (1.0 / 9.0)**depth\n", "\tprint \"t_start:\", t_start, \" t_end:\", t_end\n", "\t\t\n", "\twhile t_start < t_end:\n", "\t\tpeano = []\n", "\t\tpos = (0.0, 0.0)\n", "\t\ttemp = t_start\n", "\t\tfor i in xrange(depth):\n", "\t\t\tq = floor(9 * temp + eps / 2) #add eps/2 due to numeric issues\n", "\t\t\ttemp = 9 * temp - q\n", "\t\t\tpeano.append(q)\n", "\t\tprint peano\n", "\t\tfor i in xrange(len(peano)):\n", "\t\t\tif peano[len(peano)-i-1] == 0:\n", "\t\t\t\tpos = P0(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 1:\n", "\t\t\t\tpos = P1(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 2:\n", "\t\t\t\tpos = P2(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 3:\n", "\t\t\t\tpos = P3(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 4:\n", "\t\t\t\tpos = P4(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 5:\n", "\t\t\t\tpos = P5(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 6:\n", "\t\t\t\tpos = P6(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 7:\n", "\t\t\t\tpos = P7(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 8:\n", "\t\t\t\tpos = P8(pos)\n", " \n", "\t\tprint t_start, \" -> \", pos[0], pos[1]\n", "\t\tx.append(pos[0])\n", "\t\ty.append(pos[1])\n", "\t\tt_start = t_start + eps\n", "\n", "\t# x += [0, 0, 1, 1, 0]\n", "\t# y += [0, 1, 1, 0, 0]\n", "\tif delay > 0.0:\n", "\t\tplotCurveDelayed(x, y, delay)\n", " else:\n", " plotLineStrip(x, y, None)\n", "\t# plotLineStrip( (0,1), (0,0), None )\n", "\t# plotLineStrip( (0,0), (0,1), None )\n", "\t# plotLineStrip( (0,1), (1,1), None )\n", "\t# plotLineStrip( (1,1), (0,1), None )\n", "\n", "# plot approximatin polygon for a meander-type peano curve\n", "elif prog == 3:\n", "\teps = (1.0 / 9.0)**depth\n", "\t\n", "\tprint \"t_start:\", t_start, \" t_end:\", t_end\n", "\t\n", "\twhile t_start < t_end:\n", "\t\tpeano = []\n", "\t\tpos = (0.0, 0.0)\n", "\t\ttemp = t_start\n", "\t\tfor i in xrange(depth):\n", "\t\t\tq = floor(9 * temp + eps / 2) #add eps/2 due to numeric issues\n", "\t\t\ttemp = 9 * temp - q\n", "\t\t\tpeano.append(q)\n", "\t\tprint peano\n", "\t\tfor i in xrange(len(peano)):\n", "\t\t\tif peano[len(peano)-i-1] == 0:\n", "\t\t\t\tpos = M0(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 1:\n", "\t\t\t\tpos = M1(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 2:\n", "\t\t\t\tpos = M2(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 3:\n", "\t\t\t\tpos = M3(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 4:\n", "\t\t\t\tpos = M4(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 5:\n", "\t\t\t\tpos = M5(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 6:\n", "\t\t\t\tpos = M6(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 7:\n", "\t\t\t\tpos = M7(pos)\n", "\t\t\telif peano[len(peano)-i-1] == 8:\n", "\t\t\t\tpos = M8(pos)\n", "\n", "\t\tprint t_start, \" -> \", pos[0], pos[1]\n", "\t\tx.append(pos[0])\n", "\t\ty.append(pos[1])\n", "\t\tt_start = t_start + eps\n", "\n", "\t# x += [0, 0, 1, 1, 0]\n", "\t# y += [0, 1, 1, 0, 0]\n", "\tif delay > 0.0:\n", "\t\tplotCurveDelayed(x, y, delay)\n", "\telse:\n", "\t\tplotLineStrip(x, y, None)\n", " # plotLineStrip( (0,1), (0,0), None )\n", " # plotLineStrip( (0,0), (0,1), None )\n", " # plotLineStrip( (0,1), (1,1), None )\n", " # plotLineStrip( (1,1), (0,1), None )\n", "else:\n", "\tprint \"Error: Invalid exercise number\", Exercise\n", "\texit(1)\n" ], "language": "python", "metadata": {}, "outputs": [ { "ename": "IndentationError", "evalue": "unindent does not match any outer indentation level (, line 42)", "output_type": "pyerr", "traceback": [ "\u001b[0;36m File \u001b[0;32m\"\"\u001b[0;36m, line \u001b[0;32m42\u001b[0m\n\u001b[0;31m else:\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m unindent does not match any outer indentation level\n" ] } ], "prompt_number": 16 } ], "metadata": {} } ] }