2b:null 2c:["$","title",null,{"children":"From the Koch Snowflake to the Dragon Curve and Back | Sam Petulla | Observable"}] 31:T502,{ const wdpr = w * devicePixelRatio; const hdpr = h * devicePixelRatio; const canvas = DOM.canvas(wdpr, hdpr) const ctx = canvas.getContext('2d') canvas.style.width = `${w}px` canvas.style.height = `${h}px` const flaker = (hdpr - (offsetY)) / 1.5; ctx.translate(offsetX, (flaker / 2) - offsetY); ctx.save(); for (let j of d3.range(0, snowflakes)) { ctx.beginPath(); ctx.strokeStyle = 'red' ctx.fillStyle = 'pink' ctx.lineWidth = 1.5; ctx.lineTo(0,0); for (let i of flakeSides) { koch(flaker, flakeEdges, ctx) ctx.rotate(degree2radian(edgeRotation)) } ctx.stroke(); ctx.fill(); ctx.closePath(); ctx.restore(); ctx.save(); ctx.translate((j + 1) * flaker + (offsetX * (j + 1)), 0); } ctx.restore(); for (let j of d3.range(0, snowflakes)) { ctx.beginPath(); ctx.strokeStyle = 'red' ctx.fillStyle = 'transparent' ctx.lineWidth = 1.5; ctx.lineTo(0,0); for (let i of flakeSides) { koch(flaker, 4, ctx) ctx.rotate(degree2radian(edgeRotation)) } ctx.stroke(); ctx.fill(); ctx.closePath(); ctx.restore(); ctx.save(); ctx.translate((j + 1) * flaker + (offsetX * (j + 1)), 0); } return canvas; }32:T54d,function kochDecompose (r, order, ctx, skip) { // recursively iterate through the flake crystal angles, drawing a line at the conclusion of each recursion if (order) { // rotate angle for drawing for (let t of flakeAngles) { // recursion iterator if (order === flakeEdgesExplainDeconstruct - 1) { ctx.strokeStyle = accentColors[flakeAngles.indexOf(t)] } if (order === flakeEdgesExplainDeconstruct - 2) { ctx.globalAlpha = 0.25 + (((flakeAngles.indexOf(t) + 1 ) * 1) / (flakeEdgesExplainDeconstruct * 1.5)); } if (order === 1 && t === flakeAngles[flakeAngles.length - 1]) { ctx.lineTo(rAdjusted, 0) ctx.translate(rAdjusted, 0); ctx.stroke(); ctx.fill(); ctx.closePath(); ctx.beginPath(); ctx.lineTo((Math.sin(now / 500) + 1) * (rAdjusted), 0); ctx.translate((Math.sin(now / 500) + 1) * (rAdjusted), 0); kochDecompose(r / 3, order - 1, ctx, true) } else { kochDecompose(r / 3, order - 1, ctx) ctx.rotate(degree2radian(t)) } } } else { if (!skip) { ctx.lineTo(r, 0) ctx.translate(r, 0); } return; } }33:[] 2f:{"id":"9ece9d015090d08e","slug":null,"title":"From the Koch Snowflake to the Dragon Curve and Back","thumbnail":"c90d14eccf7f58996f8ee31c81b66170fe9a1a08d47c2c32cf629d2f6515e63c","access_level":"public","create_time":"$D2018-10-29T13:39:23.807Z","update_time":"$D2020-05-14T23:11:19.130Z","view_time":null,"first_public_time":"$D2018-12-11T16:46:48.937Z","has_unpublished_edits":null,"fork":false,"stars":15,"starred":false,"owner":{"type":"team","id":"a1d2f0b1e0240795","login":"petulla","name":"Sam Petulla ","avatar_url":"https://avatars-next.observableusercontent.com/e405f5d54370de22a4969a8b1637770aeb0f11a8d43bdfc4ccf1e2e362b8ed42","tier":"starter_2024"},"version":2788,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7d6aa91b0d5f9e4d","login":"petulla","name":"Sam Petulla ","avatar_url":"https://avatars-next.observableusercontent.com/e405f5d54370de22a4969a8b1637770aeb0f11a8d43bdfc4ccf1e2e362b8ed42","tier":null}],"members":[{"type":"individual","id":"7d6aa91b0d5f9e4d","login":"petulla","name":"Sam Petulla ","avatar_url":"https://avatars-next.observableusercontent.com/e405f5d54370de22a4969a8b1637770aeb0f11a8d43bdfc4ccf1e2e362b8ed42","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"59008c2ab3ceaa76","slug":"cs","title":"CS","owner":{"id":"a1d2f0b1e0240795","login":"petulla","name":"Sam Petulla "}},"type":"notebook","body":{"title":"From the Koch Snowflake to the Dragon Curve and Back","cells":[{"id":0,"value":"md`# From the Koch Snowflake to the Dragon Curve and Back`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2294,"value":"md`As someone who makes graphics for a living, it's difficult to look at the edge of a snowflake curve and not wonder if a dataset might map to the edge pattern.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2295,"value":"{\n const wdpr = w\n const hdpr = h\n const canvas = DOM.canvas(wdpr, hdpr * 1.4)\n const ctx = canvas.getContext('2d')\n \n ctx.setTransform(1/2, 0, 0, 1/2, 0, h/2);\n \n canvas.style.width = `${w}px`\n canvas.style.height = `${h * 1.4}px`\n \n ctx.beginPath();\n ctx.strokeStyle = '#ff5d42'\n ctx.fillStyle = '#bae0fb'\n ctx.lineWidth = 2;\n \n ctx.lineTo(10,hdpr + 50);\n ctx.translate(10,hdpr + 50);\n \n koch(1200,5,ctx);\n \n ctx.stroke();\n ctx.closePath();\n \n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2407,"value":"md` \nA closer look at the snowflake edge reveals self-similarity in the underlying structure: a set of triangles joined by line segments, joined at the same angles that compose the triangles. These recursive units compose a fractal, the [Koch Snowflake](https://babel.hathitrust.org/cgi/pt?id=inu.30000100114564;view=1up;seq=694).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2409,"value":"{\n const wdpr = w * devicePixelRatio;\n const hdpr = 2.5 * h * devicePixelRatio;\n const canvas = DOM.canvas(wdpr, hdpr)\n const ctx = canvas.getContext('2d')\n \n canvas.style.width = `${w}px`\n canvas.style.height = `${2.5 * h }px`\n while (true) {\n ctx.beginPath();\n ctx.lineWidth = 5;\n ctx.fillStyle = 'white'\n ctx.lineTo(10,hdpr - offsetY - 120);\n ctx.translate(10,hdpr - offsetY - 120);\n\n kochDecompose(300, flakeEdgesExplainDeconstruct - 1, ctx);\n \n ctx.save();\n ctx.stroke();\n ctx.closePath();\n\n for (let i of flakeSides) {\n generateSingleShape(ctx, i, nowTime + 1);\n } \n\n yield canvas;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2370,"value":"md`A crude description of each sub-triangle requires two operations {*${tex`Forward \\rightarrow`}*, ${tex`\\theta`}}: moving forward and rotating by an angle, where Theta ${tex`\\theta`} is 60 degrees rotation, and each ${tex`Forward`} line segment has length ${tex`a/3`}. \n \nBuilding from the operations to contsruct the triangle gives us something like this..`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2304,"value":"tex`Forward \\rightarrow, -\\theta,\\:Forward \\rightarrow,2\\cdot\\theta,\\:Forward \\rightarrow,-\\theta,\\:Forward \\rightarrow`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1161,"value":"canvasThree = {\n const wdpr = w ;\n const hdpr = h ;\n const canvas = DOM.canvas(wdpr, hdpr)\n const ctx = canvas.getContext('2d')\n ctx.setTransform(1/2, 0, 0, 1/2, 0, h/2);\n \n canvas.style.width = `${w}px`\n canvas.style.height = `${h}px`\n \n ctx.beginPath();\n ctx.strokeStyle = 'red'\n ctx.fillStyle = 'pink'\n ctx.lineWidth = 2.5;\n \n ctx.lineTo(10,hdpr - offsetY - 20);\n ctx.translate(10,hdpr - offsetY - 20);\n \n koch(700,2 - 1,ctx);\n ctx.fill();\n ctx.stroke();\n ctx.closePath();\n \n return canvas;\n}// break up to just the simple line","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2486,"value":"md`.. or annotated:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2305,"value":"html`

${md`[via](https://python-with-science.readthedocs.io/en/latest/koch_fractal/koch_fractal.html)`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"md`This gets us to seeing that we can build the snowflake by building small triangles. So maybe our hypothetical underlying datset for the original snowflake looks something like this: \n \n${tex`Triangle\\:, -1*\\theta,\\:Triangle,\\:2\\cdot\\theta,\\:Triangle,-1*\\theta,\\:Triangle`}\n \nOf course, that looks just like the construction of the triangle, only using our already-constructed triangles as our drawing unit rather than a line. \n \nThis helps us see that what we need is a way describe an iterator that traverses down the edges of our initial triangle. We also know that the total number of edges we draw is a product of the number of subtriangle iterations we build into our macro. \n \n\nSince there are four sides to our triangle construction, and each is decomposed into four-sided triangle sub-constructions, the number of edges for a single snowflake side is: \n \n${tex`N_{n} = N_{n-1} \\cdot 4 = 4^{n}`} \n \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2605,"value":"md` \nUse this slider to see this in action below`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1072,"value":"viewof flakeEdgesExplain = slider({\n min: 1,\n max: 5,\n step: 1,\n value: 4,\n description: \"Fractal depth\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":661,"value":"{\n const wdpr = w * 0.75;\n const hdpr = h * 0.75;\n const canvas = DOM.canvas(wdpr, hdpr)\n const ctx = canvas.getContext('2d')\n \n ctx.setTransform(1/2, 0, 0, 1/2, 0, h/3);\n \n canvas.style.width = `${w}px`\n canvas.style.height = `${h }px`\n \n ctx.beginPath();\n ctx.strokeStyle = 'red'\n ctx.fillStyle = '#bae0fb'\n ctx.lineWidth = 2.5;\n \n ctx.lineTo(10,hdpr - offsetY);\n ctx.translate(10,hdpr - offsetY);\n \n koch(700,flakeEdgesExplain,ctx);\n \n ctx.stroke();\n ctx.closePath();\n \n return canvas;\n}// break up to just the simple line","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2436,"value":"tex`N_{edges} = ${Math.pow(4,flakeEdgesExplain)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2464,"value":"md`If we take three of our snowflake constructions and combine them in a triangle, our total edges is then: \n \n${tex`N_{n} = N_{n-1} \\cdot 4 = 3 \\cdot 4^{n}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2514,"value":"md`Two sides winding into configuration looks like this:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1262,"value":"html`${Math.round(edgeRotation * (Math.sin(now / 1500) + 1) / 2,3) + ' degrees of rotation'}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1122,"value":"{\n const wdpr = 600;\n const hdpr = h * 2;\n \n const canvas = DOM.canvas(wdpr, hdpr)\n const ctx = canvas.getContext('2d')\n ctx.setTransform(1/2, 0, 0, 1/2, 0, 0);\n \n canvas.style.width = `${600}px`\n canvas.style.height = `${h * 2}px`\n while (true) {\n ctx.clearRect(0, 0, wdpr, hdpr);\n\n ctx.beginPath();\n ctx.strokeStyle = 'red'\n ctx.fillStyle = 'pink'\n ctx.lineWidth = 3;\n\n ctx.lineTo(80,h);\n ctx.translate(80,h);\n\n koch(500,flakeEdgesExplain,ctx);\n ctx.rotate(degree2radian(edgeRotation * (nowTime + 1) / 2))\n koch(500,flakeEdgesExplain,ctx);\n\n ctx.stroke();\n ctx.fill();\n ctx.closePath();\n return canvas\n }\n}// break up to just the simple line","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2500,"value":"md`This is all well and fine but we still don't have a dataset to describe our fractal: If we were being absurdly verbose, we might have a data cell for every iteration down from our initial four-edged triangle construction, all the way down to the *n* iteration level. We'd also of course need to indicate our constant theta. Let's see if we can [explore](https://simblob.blogspot.com/2007/07/interactive-illustrations.html) this decomposition further and try to simplify.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":558,"value":"viewof flakeEdges = slider({\n min: 0,\n max: 4,\n step: 1,\n value: 2,\n description: \"Exposed fractal depth\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2530,"value":"md`A better way might be to define a function that calls itself at every edge of the fractal as it iterates. Rather than draw the edge straight across, it would draw a triangle in that spot instead -- and so on, until the *nth* iteration.\n \nIn fact, we only need 10 lines of code (without the boilerplate) to match the internal state described above: a rotation according to *Theta*, a decrementer that drops down one level, and translation after rotation. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"function koch (r, order, ctx) {\n // recursively iterate through the flake crystal angles, \n // drawing a line at the conclusion of each recursion\n if (order) {\n // rotate angle for drawing\n // iterate through [-60, 120, -60, 0]\n // -theta, 2*theta, -theta, 0 \n for (let t of flakeAngles) {\n // recursion iterator\n koch(r / 3, order - 1, ctx)\n // left rotation iterator\n ctx.rotate(degree2radian(t))\n }\n } else {\n // draw line\n ctx.lineTo(r, 0)\n ctx.translate(r, 0)\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2463,"value":"md`But what if we could describe this even more succinctly, so we don't have to go through the trouble of setting in stone the edge rotation or the translation pattern. \n \nIt would be a lot easier to give a set of instructions. We'd provide our crude formula, the iterations *n*, and then generate an instruction sheet by recursively replacing parts of our original formula with the full formula, and so on. Then our dataset doesn't need to be a dataset of specific values at at all but a grammar.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2661,"value":"md`### Lindenmayer grammar`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2555,"value":"md`*Lindenmayer systems*, or *L-systems*, do exactly this. Our single snowflake edge at the top can be described thusly, for various levels of iteration. \n \nIn this grammar, *-* and *+* describe ${tex`-\\theta\\:and \\:\\theta`}. *F* is a forward movement.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2241,"value":"html `n = 0 | F
\nn = 1 | F-F++F-F
\nn = 2 | F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F
\nn = 3 | F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F
\n...`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2561,"value":"md`If this is confusing, match the *n=1* line with our crude ${tex`Forward \\rightarrow -\\theta`} formula above. Or, think of how each iteration replaces each *Forward* line within its parent iteration with the original four-line triangle formula definition.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2274,"value":"html`n = 2*| (F-F++F-F)-(F-F++F-F)++(F-F++F-F)-(F-F++F-F)
`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":659,"value":"md`Another way you might construct a grammar is with [Thue-Morse](https://progur.com/2016/10/procedural-generation-create-koch-curve-javascript.html) sequences, which encode forward and angular movement with 1's and 0's.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2581,"value":"md`Once we've built a grammar like this, our job is much easier: After generating a string of instructions, we can split them by character and map a drawing operation performed on a canvas to each character.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2582,"value":"md`The below editor allows you to try three pre-built systems and adjust angle and iteration, while seeing the grammar of the system. You can even nest your systems, to simplify your notation. In the case of the Dragon Curve, the instructions *X* and *Y* behave the same as *F* in the Koch example, replacing prior instances of *X* and *Y* with an instruction set and corresponding to *Forward* on its own.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2056,"value":"html`${__L.label}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2190,"value":"html`
L-System
${Object.keys(__L.system).map(key => key + ': ' + __L.system[key]).reduce((w,z) => w + ',
' + z)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2032,"value":"viewof _angle = text({title: \"Grammar Angle (Coded as +)\", value: __L.angle})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1755,"value":"{\n const c = DOM.context2d(w, h*3);\n \n c.canvas.value = c;\n c.resetTransform();\n c.setTransform(1/2, 0, 0, 1/2, w / 2, 0);\n \n \n drawKoch(c);\n return c.canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1990,"value":"viewof __L = {\n const systems = [{\n label: 'Koch Snowflake',\n axiom: 'F++F++F',\n system: {\n 'F': 'F-F++F-F',\n },\n angle: 60,\n scale: 20,\n top: 25,\n left: -250,\n iterations: 4\n },\n {\n label: 'Dragon Curve',\n axiom: 'FX',\n system: {\n X: 'X+YF+',\n Y: '-FX-Y',\n },\n angle: 90,\n scale: 6,\n top: 1400,\n left: 500,\n iterations: 14\n },\n {\n label: 'Koch Anti-Snowflake',\n axiom: 'F++F++F',\n system: {\n 'F': 'F+F--F+F',\n },\n angle: 60,\n scale: 20,\n top: 0,\n left: -250,\n iterations: 4\n }]\n let _value = systems[1];\n const view = html`${systems.map((d, i) => { \n const div = html`