31:T780,md`# Iterated Function Systems From [Wikipedia](https://en.wikipedia.org/wiki/Iterated_function_system): >In mathematics, iterated function systems (IFSs) are a method of constructing fractals; the resulting fractals are often self-similar. IFS fractals are more related to set theory than fractal geometry.[1] They were introduced in 1981. >IFS fractals, as they are normally called, can be of any number of dimensions, but are commonly computed and drawn in 2D. The fractal is made up of the union of several copies of itself, each copy being transformed by a function (hence "function system"). The canonical example is the Sierpiński triangle. The functions are normally contractive, which means they bring points closer together and make shapes smaller. Hence, the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself, ad infinitum. This is the source of its self-similar fractal nature. In this notebook, we provide a way to explore linear IFS's, i.e., those based on linear transformations. The idea is to edit a set of triangles that encode the individual transformations and watch the resulting fractals. It is also a good way to visualize Barnsley's [collage theorem](https://en.wikipedia.org/wiki/Collage_theorem). We provide a few famous IFS's so you can start exploring (credits: [Larry Riddle's blog](https://larryriddle.agnesscott.org/ifs/ifs.htm), [Coloring Schemes and the Dynamical Structure of Iterated Function Systems by Michael Frame and Lynne Erdman](https://doi.org/10.1063/1.4822942)). About the triangle editing interface: transformations are modified by dragging either the triangles themselves (translation) or the anchors on each triangle. Some anchors (squares) allow for scaling, the solid round anchors can be used to rotate the triangle, and the dashed round anchors can be freely moved. `32:T89f,render = { newFractal; let [w,h] = [width,~~(width*9/16)] let ctx = DOM.context2d(w,h) // Thanks to Fabian Iwand for pointing out that a white background is better than transparent ctx.fillStyle = 'white'; ctx.fillRect (0,0,w,h) let canvas = ctx.canvas let transf = gui.transformations(); let n = 50; let probMap = function() { // Probabilistic map with n slots for sampling the transformations let dets = transf.map(t=>Math.abs(t.a*t.d-t.b*t.c)+0.01); let detsum = dets.reduce((a,b) => a+b) let p = dets.map(d => d/detsum); for (let i = 1; i < p.length; i++) p[i] += p[i-1]; let pmap = []; for (let j = 0; j < n; j++) { let k = 0; for (let i = 0; i < p.length && p[i] < j/n; i++) k++; pmap[j] = k; } return pmap }(); let lastPoint = Vec(0,0) let lastTransf = [] let ntransf = 0 let transfHistorySize = 8 let newPoint = () => { let itransf = probMap[~~(Math.random()*n)] lastTransf [(ntransf++)%transfHistorySize] = itransf lastPoint = transf[itransf].apply(lastPoint) return lastPoint; } let batch = function* (batchSize) { for (let i = 0; i < batchSize; i++) yield newPoint() } // Throw away a first batch for (let p of batch(600)) {}; // Get a bounding box let mbr = new MBR(...batch(1000)); let size = mbr.size() let aspect = size.x/size.y; // Compute a viewport transformation let viewport = viewportTransf(30,w,h,mbr); let idrequest; function refresh () { for (let p of batch(1000)) { p = viewport.apply(p) ctx.fillStyle = palette[lastTransf[(ntransf-renderColorLevel)%transfHistorySize]%palette.length] ctx.fillRect (p.x, p.y, pointSize, pointSize) } idrequest = requestAnimationFrame (refresh) } idrequest = requestAnimationFrame (refresh) invalidation.then(() => {cancelAnimationFrame(idrequest)}) return canvas // for (let i = 0; i < 1000; i++) { // for (let p of batch(1000)) { // p = viewport.apply(p) // ctx.fillStyle = palette[lastTransf[(ntransf-renderColorLevel)%transfHistorySize]%palette.length] // ctx.fillRect (p.x, p.y, 0.5, 0.5) // } // yield canvas; // } } 33:T616,{ let reset = html``; let fractal = select({options:Object.keys(presets)}); fractal.style.display = 'inline-block'; reset.onclick = () => { gui.reset(presets[fractal.value]); gui.refresh() } fractal.addEventListener ('input', reset.onclick) let add = html``; add.onclick = () => { gui.addTriangle(); } let del = html``; del.onclick = () => { gui.delTriangle(); } let level = select({options:[1,2,3,4,5,6,7]}) let colorLevel = select({options:[1,2,3,4,5,6,7]}) level.style.display = 'inline-block'; colorLevel.style.display = 'inline-block'; level.addEventListener ('input', e => { gui.setLevel(level.value) }) colorLevel.addEventListener ('input', e => { mutable renderColorLevel = colorLevel.value }) let paletteSelector = select({options:Object.keys(palettes)}) paletteSelector.style.display = 'inline-block'; paletteSelector.addEventListener ('input', e => { mutable palette = palettes[paletteSelector.value];gui.refresh() }) let pointSizeSelector = select({options:[0.1,0.5,1,2], value:0.5}) pointSizeSelector.style.display = 'inline-block'; pointSizeSelector.addEventListener ('input', e=> { mutable pointSize = pointSizeSelector.value}) return html`

${reset} ${fractal} ${add} ${del}
Levels shown in GUI: ${level} Point size: ${pointSizeSelector} Render coloring level: ${colorLevel} Color palette: ${paletteSelector}

`; }34:Tbef,viewof gui = { let [w,h] = [width,~~(width*9/16)] let ctx = DOM.context2d(w,h) let canvas = ctx.canvas let margin = 40 let side = h - 2 * margin; let root,triangles; let level = 1; let reset = (newtransformations) => { // Find bounding box let mbr = new MBR(...newtransformations.map(t => t.apply(Vec(0,0))) .concat(newtransformations.map(t => t.apply(Vec(1,1))))); let viewport = viewportTransf(margin, w, h, mbr); let basis = new Tri(Vec(0,0), Vec(0,1), Vec(1,0)) root = //new Tri(Vec(margin,margin),Vec(margin,margin+side),Vec(margin+side,margin)); basis.transformed(viewport); let T = basis.transformation(root); triangles = []; for (let transf of newtransformations) { let tri = basis.transformed(transf).transformed(T) triangles.push(tri) } } reset(presets.tree); let transformations = () => { let basis = new Tri(Vec(0,0), Vec(0,1), Vec(1,0)) let T = basis.transformation(root); let Tinv = root.transformation (basis); return triangles.map((tri)=>basis.transformation(tri.transformed(Tinv))); } let computeFractal = () => { let transf = triangles.map((tri)=>root.transformation(tri)) let fractal = [root]; for (let i = 0; i < level; i++) { let temp = [] for (let tri of fractal) { for (let t of transf) { temp.push (tri.transformed(t)) } } fractal = temp; } return fractal } let refresh = () => { ctx.clearRect(0,0,w,h) ctx.fillStyle = 'rgb(30,30,30)'; ctx.strokeStyle = 'rgba(0,0,0,0)'; let i = 0; for (let t of computeFractal()) { ctx.fillStyle = mutable palette[i%triangles.length] i = i+1 t.draw(ctx) } ctx.fillStyle = 'rgba(200,200,255,0.2)' root.draw(ctx) for (let t of triangles) { ctx.fillStyle = 'rgba(255,200,200,0.2)'; ctx.strokeStyle = 'rgba(255,0,0,0.5)' t.draw(ctx) ctx.strokeStyle = 'rgba(255,0,0,1)' ctx.fillStyle = 'white'; t.drawAnchors(ctx) } mutable newFractal++ } refresh() let drag = null; let selected = -1; canvas.onmousedown = (e) => { let mouse = Vec (e.offsetX, e.offsetY); drag = null; selected = -1; for (let i = 0; i < triangles.length; i++) { let t = triangles[i]; let pick = t.pick(mouse); if (pick) { drag = pick selected = i; } } } canvas.onmousemove = (e) => { if (drag && e.buttons) { drag(Vec (e.offsetX, e.offsetY)); refresh() } } let addTriangle = () => { reset (transformations().concat( [Matrix.translate(Math.random()/2,Math.random()/2).mult (Matrix.scale(0.5,0.5))])); refresh() } let delTriangle = () => { if (selected >= 0) { triangles.splice (selected, 1) refresh() } } let setLevel = (l) => { level= l refresh() } canvas.value = {reset,refresh, addTriangle, delTriangle, setLevel, transformations} return canvas } 35:T130a,// // Represents a triangle (3 points). Transformations are mappings between triangles in 2D // class Tri { constructor (a,b,c) { Object.assign(this,{a,b,c}) } // Returns a copy of this triangle clone () { return new Tri (this.a.clone(),this.b.clone(),this.c.clone()) } // Scales this triangle by factor around its center scale (factor) { let {a,b,c} = this; let center = this.center; for (let p of [a,b,c]) { let v = p.sub(center); v = v.scale (factor) p.set (center.add(v)) } return this } // Translates this triangle by v translate (v) { for (let p of [this.a,this.b,this.c]) { p.set (p.add (v)); } return this } // Returns the transformation matrix that maps the vertices of // this triangle to the vertices of triangle t2 transformation(t2) { let {a,b,c} = this; let m1 = [a.x,a.y,1, b.x,b.y,1, c.x,c.y,1]; let m2 = [t2.a.x,t2.a.y,1, t2.b.x,t2.b.y,1, t2.c.x,t2.c.y,1]; let m1i = mat3.invert([],m1) let t = mat3.mul([],m2,m1i); return new Matrix (t[0],t[1], t[3], t[4], t[6], t[7]) } // Returns this triangle transformed by t transformed (t) { return new Tri(t.apply(this.a), t.apply(this.b), t.apply(this.c)) } // Barycenter of the triangle get center () { return this.a.add(this.b).add(this.c).scale(1/3) } // Returns a drag function if an anchor point is picked or null otherwise pick (mouse) { let oldpos = mouse; // Returns a drag function that rotates the triangle around center let rotate = (center) => { return (newpos) => { let v1 = oldpos.sub(center) let v2 = newpos.sub(center) let ang = v2.signedAngle(v1) let transf = Matrix.translate(center.x,center.y) .mult(Matrix.rotate(ang)) .mult(Matrix.translate(-center.x,-center.y)); for (let p of [this.a,this.b,this.c]) p.set (transf.apply(p)) } } // Returns a function that drags vertex p along direction v let dragVertexOnLine = (p, v) => { v = v.normalize() return (newpos) => { let u = newpos.sub(oldpos); let d = u.dot(v) p.set(p.add(v.scale(d))) } } // Returns a function that drags p along direction v considering only the motion along n let dragVertexOnProj = (p, v, n) => { v = v.normalize() n = n.normalize() let cos = n.dot(v) return (newpos) => { let u = n.scale(newpos.sub(oldpos).dot(n)); let d = u.dot(v)/cos/cos p.set(p.add(v.scale(d))) } } // Returns a function that drags that particular anchor // (corner points) for (let p of [this.b,this.c]) { if (p.dist(mouse) <= 5) { let func = rotate(this.center); return (newpos) => { func(newpos); oldpos = newpos } } } // (origin point) for (let p of [this.a]) { if (p.dist(mouse) <= 5) { return (newpos) => { p.set (p.add (newpos.sub(oldpos))); oldpos = newpos } } } // (edge points) let ab = this.a.add(this.b).scale(0.5); if (ab.dist(mouse) <= 5) { let vac = this.a.sub(this.c); let vbc = this.b.sub(this.c); let funca = dragVertexOnProj(this.a, vac, vac); let funcb = dragVertexOnProj(this.b, vbc, vac); return (newpos)=> { funca(newpos); funcb(newpos); oldpos = newpos; } } let ac = this.a.add(this.c).scale(0.5); if (ac.dist(mouse) <= 5) { let vab = this.a.sub(this.b); let vcb = this.c.sub(this.b); let funca = dragVertexOnProj(this.a, vab, vab); let funcc = dragVertexOnProj(this.c, vcb, vab); return (newpos)=> { funca(newpos); funcc(newpos); oldpos = newpos; } } // Clicked inside triangle? if (Math.abs(mouse.orient(this.a,this.b)+mouse.orient(this.b,this.c)+mouse.orient(this.c,this.a))==3) { return (newpos) => { this.translate (newpos.sub(oldpos)) oldpos = newpos } } return null } // Draws this triangle onto canvas with context ctx draw (ctx) { let {a,b,c} = this; ctx.beginPath(); ctx.moveTo (a.x,a.y) ctx.lineTo (b.x,b.y) ctx.lineTo (c.x,c.y) ctx.closePath() ctx.fill() ctx.stroke() } drawAnchors(ctx) { let {a,b,c} = this; let ab = this.a.add(this.b).scale(0.5); let ac = this.a.add(this.c).scale(0.5); ctx.setLineDash([2,2]) for (let p of [a,b,c]) { ctx.beginPath() ctx.arc (p.x,p.y,5,0,Math.PI*2) ctx.fill() ctx.stroke() ctx.setLineDash([]) } for (let p of [ab,ac]) { ctx.fillRect(p.x-5,p.y-5,10,10) ctx.strokeRect(p.x-5,p.y-5,10,10) } } }36:Ta16,// // Some well-known IFSs // presets = ({ tree: [ // From https://doi.org/10.1063/1.4822942 Matrix.scale(0.05, 0.6), Matrix.translate(0,1).mult(Matrix.scale(0.05,-0.5)), new Matrix(0.46, 0.39, -0.32, 0.38, 0, 0.6), new Matrix(0.47, 0.17, -0.15, 0.42, 0, 1.1), new Matrix(0.43, -0.25, 0.28, 0.45, 0, 1), new Matrix(0.42, -0.35, 0.26, 0.31, 0, 0.7) ], "Sierpinski gasket": [ Matrix.translate(0.5,0.0).mult(Matrix.scale(0.5,0.5)), Matrix.translate(0.0,0.5).mult(Matrix.scale(0.5,0.5)), Matrix.translate(0.0,0.0).mult(Matrix.scale(0.5,0.5)) ], "Sierpinski pentagon": [ new Matrix(0.382, 0, 0, 0.382, 0, 0), new Matrix(0.382, 0, 0, 0.382, 0.618, 0), new Matrix(0.382, 0, 0, 0.382, 0.809, 0.588), new Matrix(0.382, 0, 0, 0.382, 0.309, 0.951), new Matrix(0.382, 0, 0, 0.382, -0.191, 0.588), ], "Sierpinski carpet": [ new Matrix(1/3, 0,0, 1/3, 0, 0), new Matrix(1/3, 0,0, 1/3, 1/3, 0), new Matrix(1/3, 0,0, 1/3, 0, 1/3), new Matrix(1/3, 0,0, 1/3, 2/3, 0), new Matrix(1/3, 0,0, 1/3, 0, 2/3), new Matrix(1/3, 0,0, 1/3, 2/3, 2/3), new Matrix(1/3, 0,0, 1/3, 1/3, 2/3), new Matrix(1/3, 0,0, 1/3, 2/3, 1/3), ], "Heighway dragon": [ new Matrix(1/2, 1/2, -1/2, 1/2, 0, 0), new Matrix(-1/2, 1/2, -1/2, -1/2, 1, 0), ], "Levi dragon": [ new Matrix(1/2, 1/2, -1/2, 1/2, 0, 0), new Matrix(1/2, -1/2, 1/2, 1/2, 1/2, 1/2), ], "Koch curve": [ Matrix.scale(1/3,1/3), Matrix.scale(1/3,1/3).mult(Matrix.translate(2,0)), Matrix.scale(1/3,1/3).mult(Matrix.translate(1,0)).mult(Matrix.rotate(Math.PI/3)), Matrix.scale(1/3,1/3).mult(Matrix.translate(1.5, Math.sqrt(3)/2)).mult(Matrix.rotate(-Math.PI/3)) ], "McWorter Pentigree" : [ Matrix.rotate(rad(36)).mult(Matrix.scale(0.381966,0.381966)), Matrix.translate(0.309,0.225).mult(Matrix.rotate(rad(108))).mult(Matrix.scale(0.381966,0.381966)), Matrix.translate(0.191,0.588).mult(Matrix.rotate(rad(-36))).mult(Matrix.scale(0.381966,0.381966)), Matrix.translate(0.500,0.363).mult(Matrix.rotate(rad(-108))).mult(Matrix.scale(0.381966,0.381966)), Matrix.translate(0.382,0).mult(Matrix.rotate(rad(-36))).mult(Matrix.scale(0.381966,0.381966)), Matrix.translate(0.691,-0.225).mult(Matrix.rotate(rad(36))).mult(Matrix.scale(0.381966,0.381966)), ], "Barnsley fern" : [ // Barnsley Fern new Matrix(0.01, 0, 0, 0.16, 0, 0), new Matrix(0.85, -0.04, 0.04, 0.85, 0, 1.60), new Matrix(0.20, 0.23, -0.26, 0.22, 0, 1.60), new Matrix(-0.15, 0.26, 0.28, 0.24, 0, 0.44) ], })37:[] 2f:{"title":"Iterated Function Systems","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":294,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":424,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":491,"value":"md`### The Tri (triangle) class`","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":474,"value":"md`### GUI variables`","pinned":true,"hidden":false,"mode":"ojs"},{"id":328,"value":"mutable newFractal = 0","pinned":true,"hidden":false,"mode":"ojs"},{"id":458,"value":"mutable renderColorLevel = 1","pinned":true,"hidden":false,"mode":"ojs"},{"id":399,"value":"mutable palette = palettes.A","pinned":true,"hidden":false,"mode":"ojs"},{"id":496,"value":"mutable pointSize = 0.5","pinned":true,"hidden":false,"mode":"ojs"},{"id":478,"value":"md`### Geometry utils`","pinned":false,"hidden":false,"mode":"ojs"},{"id":367,"value":"// Computes a transformation to map the mbr onto\n// a rectangular area of width w and height h framing it with 'margin' pixels\nviewportTransf = function(margin,w,h,mbr) {\n let [W,H] = [w-2*margin,h-2*margin]\n let size = mbr.size();\n let aspect = size.x/size.y;\n\n if (aspect < W/H) {\n let scale = H/size.y;\n let dx = (W-size.x*scale)/2;\n return Matrix.translate(0,h)\n .mult(Matrix.scale(1,-1))\n .mult(Matrix.translate(dx+margin,margin))\n .mult(Matrix.scale(scale,scale))\n .mult(Matrix.translate(-mbr.min.x, -mbr.min.y))\n }\n else {\n let scale = W/size.x;\n let dy = (H-size.y*scale)/2;\n return Matrix.translate(0,h)\n .mult(Matrix.scale(1,-1))\n .mult(Matrix.translate(margin,dy+margin))\n .mult(Matrix.scale(scale,scale))\n .mult(Matrix.translate(-mbr.min.x, -mbr.min.y))\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":446,"value":"rad = deg => deg/180*Math.PI","pinned":true,"hidden":false,"mode":"ojs"},{"id":274,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":394,"value":"//\n// Some color palettes\n//\npalettes = ({\n A: ['#1b9e77','#d95f02','#7570b3','#e7298a','#66a61e','#e6ab02','#a6761d'],\n B: ['#7fc97f','#beaed4','#fdc086','#ffff99','#386cb0','#f0027f','#bf5b17'],\n C: ['#66c2a5','#fc8d62','#8da0cb','#e78ac3','#a6d854','#ffd92f','#e5c494'],\n greens: ['#99d8c9','#66c2a4','#41ae76','#238b45','#006d2c','#00441b'].reverse(),\n oranges: ['#feedde','#fdd0a2','#fdae6b','#fd8d3c','#f16913','#d94801','#8c2d04'].reverse(),\n purpleRed: ['#f1eef6','#d4b9da','#c994c7','#df65b0','#e7298a','#ce1256','#91003f'].reverse(),\n reds: ['#e00','#a00', '#700', '#300', '#000'],\n blues: ['#02f','#02a', '#027', '#004', '#000'],\n grays: ['#ccc','#aaa', '#888', '#444', '#222', '#000'],\n black: ['#000']\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":123,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"import {Vec,Matrix,MBR} from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":75,"value":"glmatrix = require('https://bundle.run/gl-matrix@3.3.0')","pinned":true,"hidden":false,"mode":"ojs"},{"id":78,"value":"mat3 = glmatrix.mat3","pinned":true,"hidden":false,"mode":"ojs"},{"id":131,"value":"import {select} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}