31:Te01,FileAttachment("twin_boundary_parts.png").image({ width: width < 900 ? width : 900 }) // { // let w = width < 800 ? width : 800; // let h = w; // let canvas = d3.create("canvas").attr("width", w).attr("height", h).node(); // let xmin = -2; // let xmax = 2; // let ymin = -1.5; // let ymax = 2.5; // let xscale = d3.scaleLinear().domain([xmin, xmax]).range([0, w]); // let yscale = d3.scaleLinear().domain([ymin, ymax]).range([h, 0]); // let context = canvas.getContext("2d"); // context.beginPath(); // context.fillStyle = "#DD1600"; // attractor.forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // // East // context.beginPath(); // context.fillStyle = "lightgray"; // attractor // .map((a) => a.map(([x, y]) => [x + 1, y])) // .forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // // North East // context.beginPath(); // context.fillStyle = "gray"; // attractor // .map((a) => a.map(([x, y]) => [x + 1, y + 1])) // .forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // // North // context.beginPath(); // context.fillStyle = "lightgray"; // attractor // .map((a) => a.map(([x, y]) => [x, y + 1])) // .forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // // West // context.beginPath(); // context.fillStyle = "gray"; // attractor // .map((a) => a.map(([x, y]) => [x - 1, y])) // .forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // // South West // context.beginPath(); // context.fillStyle = "lightgray"; // attractor // .map((a) => a.map(([x, y]) => [x - 1, y - 1])) // .forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // // South // context.beginPath(); // context.fillStyle = "gray"; // attractor // .map((a) => a.map(([x, y]) => [x, y - 1])) // .forEach(function (r) { // context.moveTo(xscale(r[0][0]), yscale(r[0][1])); // r.slice(1).forEach((pt) => context.lineTo(xscale(pt[0]), yscale(pt[1]))); // }); // context.fill(); // context.closePath(); // let all_pts = digraphIFS2.generate_stochastic(60000); // all_pts.slice(0, -1).forEach(function (pts, i) { // pts.forEach(function (pt) { // context.beginPath(); // if (i % 2 == 0) { // context.fillStyle = "#333"; // } else { // context.fillStyle = "#880800"; // } // context.moveTo(xscale(pt[0]), yscale(pt[1])); // context.arc(xscale(pt[0]), yscale(pt[1]), 1, 0, 2 * Math.PI); // context.fill(); // context.closePath(); // }); // }); // return canvas; // }32:Ta9e,Suppose that ${tex`T`} is a self-affine tile and there is a lattice ${tex`\Gamma`} of points in the plane so that the translates of ${tex`T`} by the points of ${tex`\Gamma`} form a tiling of the plane. The lattice should be invariant under the action of ${tex`A`} in the sense that ${tex`A (\Gamma ) \subset \Gamma`}. (Note that the lattice condition is frequently, but not always satisfied by ${tex`\mathbb Z \times \mathbb Z`}.) Given ${tex`\alpha \in \Gamma`}, define ${tex.block`T_{\alpha}=T\cap (T+\alpha).`} The boundary of ${tex`T`} is formed by the collection of sets ${tex`T_{\alpha }`} which are non-empty, excluding the case ${tex`\alpha =0`}. It turns out that these sets ${tex`T_{\alpha }`} display mixed self-similarity; i.e., if we let ${tex.block`\mathcal{F}=\left\{\alpha \in \Gamma :T_{\alpha}\neq \emptyset \text{ and } \alpha \neq 0\right\},`} then the collection ${tex`\left\{T_{\alpha }:\alpha \in \mathcal{F}\right\}`} forms the invariant list of a digraph IFS. This can be demonstrated by examining how the expansion matrix ${tex`A`} affects each set ${tex`T_{\alpha }`} and then translating to a digraph IFS by applying ${tex`A^{-1}`} as follows:: ${tex.block` \begin{aligned} A\left(T_{\alpha }\right) &= A(T) \cap A(T+\alpha )\\ &= \left(\underset{d\in \mathcal{D}}{\bigcup }(T+d)\right)\bigcap \text{ }\left(\underset{d'\in \mathcal{D}}{\bigcup }(T+d'+A \alpha )\right)\\ &= \underset{d,d'\in \mathcal{D}}{\bigcup }\left((T+d)\bigcap (T+d'+A \alpha )\right)\\ &= \underset{d,d'\in \mathcal{D}}{\bigcup }\left[(T\bigcap (T-d+d'+A \alpha ))+d\right]\\ &= \underset{d,d'\in \mathcal{D}}{\bigcup }\left(\left(T_{A \alpha -d+d'}\right)+d\right). \end{aligned}`} We are only interested in the non-empty intersections so, given ${tex`\alpha`} and ${tex`\beta`} in ${tex`\mathcal{F}`}, let ${tex`M(\alpha ,\beta )`} denote the set of pairs of digits ${tex`(d,d')`} so that ${tex`\beta =A \alpha -d+d'`}. Then applying ${tex`A^{-1}`} to both sides of the equation we just derived, we see that ${tex.block`T_{\alpha }=\underset{\beta \in \mathcal{F}}{\bigcup } \: \: \underset{(d,d')\in M(\alpha ,\beta )}{\bigcup }\left(A^{-1}T_{\beta }+A^{-1}d\right).`} This equation defines a digraph IFS to generate the sets ${tex`T_{\alpha }`}. The nodes are exactly the elements of ${tex`\mathcal F`}. Given ${tex`\alpha`} and ${tex`\beta`} in ${tex`\mathcal{F}`}, the functions mapping ${tex`T_{\beta }`} into ${tex`T_{\alpha }`} are precisely those affine functions defined by ${tex`\left\{A^{-1},A^{-1}d\right\}`} for all digits ${tex`d`} so that there is a digit ${tex`d'`} satisfying ${tex`\beta = A \alpha -d+d'`}. This strategy to generate the digraph IFS is implemented in the following code:33:[{"id":"06a39a4a4411aba21183b0c948eeb2e5addbabde0c937cbaac282ddf8e8e7263f7274c3347149868604fb407d1742af18438e8a29c1b2644927b022344bf84e4","href":"https://static.observableusercontent.com/files/06a39a4a4411aba21183b0c948eeb2e5addbabde0c937cbaac282ddf8e8e7263f7274c3347149868604fb407d1742af18438e8a29c1b2644927b022344bf84e4","name":"twin_boundary.png","type":"image/png","lastModified":1636937050954.714,"size":366041},{"id":"fec2408d0cf0ba332674449a9d3e13f0d9cc4dab7dc38420116b6a9e287db927d81e71bb4dcaad13ec513db979a32e5f0f625f3c2a5bf87436252407ef52b1f5","href":"https://static.observableusercontent.com/files/fec2408d0cf0ba332674449a9d3e13f0d9cc4dab7dc38420116b6a9e287db927d81e71bb4dcaad13ec513db979a32e5f0f625f3c2a5bf87436252407ef52b1f5","name":"twin_full_boundary.png","type":"image/png","lastModified":1638203565496.948,"size":134349},{"id":"2bbe0ffba5dc7bd232a13f0fa512df97f71a2c1a37f2a028bf5e0833dfb0f1a1ee1a839567cc5cf8253d3fff445548d8e4e01b017132202b1f9c5ac5cea39d8b","href":"https://static.observableusercontent.com/files/2bbe0ffba5dc7bd232a13f0fa512df97f71a2c1a37f2a028bf5e0833dfb0f1a1ee1a839567cc5cf8253d3fff445548d8e4e01b017132202b1f9c5ac5cea39d8b","name":"twin_boundary_parts.png","type":"image/png","lastModified":1638204391809.307,"size":99449}] 2f:{"title":"The Twindragon (with boundary)","cells":[{"id":0,"value":"# The Twindragon (with boundary)\n\nThe twindragon is a two-dimensional, self-similar set with a fractal boundary that's described in [this notebook](https://observablehq.com/@mcmcclur/the-twindragon). The purpose of this new notebook is to investigate the boundary of the twindragon - part of which is highlighted in the image below.","pinned":false,"hidden":false,"mode":"md"},{"id":368,"value":"FileAttachment(\"twin_boundary.png\").image({ width: width < 900 ? width : 900 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":487,"value":"Here's an image of just one twindragon with its full boundary. Note that both of these images are pre-generated; the code is in this notebook, though some is commented out.","pinned":false,"hidden":false,"mode":"md"},{"id":437,"value":"FileAttachment(\"twin_full_boundary.png\").image({\n width: width < 600 ? width : 600\n})\n\n// {\n// let w = width < 600 ? width : 600;\n// let h = (2 * w) / 1.75;\n// let c1 = IFS.render_deterministic({\n// max_depth: 15,\n// image_width: w,\n// image_height: h,\n// init: [\n// [0, 0],\n// [1, -1],\n// [2, 0],\n// [1, 1]\n// ],\n// colors: [\"lightgray\", \"lightgray\"],\n// extent: [\n// [-1, 0.75],\n// [-0.5, 1.5]\n// ],\n// padding: 0\n// });\n\n// let ctx = c1.getContext(\"2d\");\n// let pts = digraphIFS2.generate_stochastic(60000)[6];\n\n// pts.forEach(function (pt) {\n// ctx.beginPath();\n// ctx.fillStyle = \"black\";\n// ctx.moveTo(IFS.xScale(pt[0]), IFS.yScale(pt[1]));\n// ctx.arc(IFS.xScale(pt[0]), IFS.yScale(pt[1]), 1, 0, 2 * Math.PI);\n// ctx.fill();\n// ctx.closePath();\n// });\n\n// return c1;\n// }","pinned":false,"hidden":false,"mode":"ojs"},{"id":893,"value":"## Finding the boundary\n\nAs it turns out, the boundary consists of a collection of parts that display *mixed self-similarity*, as described in [this notebook](https://observablehq.com/@mcmcclur/mixed-self-similarity). The individual pieces are exactly the intersections between the set and its translates that meet the set. More precisely, the sets ${tex`T_{\\alpha}`} of the form\n${tex.block`T_{\\alpha} = T \\cap (T+\\alpha),`}\nwhere ${tex`\\alpha \\in \\{\\langle1,0\\rangle,\\langle1,1\\rangle,\\langle0,1\\rangle,\\langle-1,0\\rangle,\\langle-1,-1\\rangle,\\langle0,-1\\rangle\\}`}. These sets are shown in the image below:","pinned":false,"hidden":false,"mode":"md"},{"id":645,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1041,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":956,"value":"// Note that the matrix AInv, the digit set D,\n// and the set of shifts F are defined below.\n\ndigraphIFS = {\n let edges = [];\n let eps = 0.00000001;\n for (let i = 0; i < F.length; i++) {\n for (let j = 0; j < F.length; j++) {\n D.forEach(function (d) {\n D.forEach(function (dp) {\n let alpha = F[i];\n let beta = F[j];\n let Aalpha = math.multiply(A, alpha);\n let x = Aalpha[0] + dp[0] - d[0];\n let y = Aalpha[1] + dp[1] - d[1];\n if (math.abs(x - beta[0]) < eps && math.abs(y - beta[1]) < eps) {\n edges.push({\n source: i,\n target: j,\n f: new AffineFunction([AInv, math.multiply(AInv, d)])\n });\n }\n });\n });\n }\n }\n return new DigraphIFS(edges);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":971,"value":"There's quite a lot we can do with the digraph IFS in hand. Here's the fractal dimension of the boundary, for example:","pinned":false,"hidden":false,"mode":"md"},{"id":1071,"value":"digraphIFS.dimension","pinned":true,"hidden":false,"mode":"ojs"},{"id":1067,"value":"Clearly, the computed dimension is a numerical approximation. In this particular case, we can find it in closed form. We might begin with the digraph that describes how the pieces fit together:","pinned":false,"hidden":false,"mode":"md"},{"id":967,"value":"digraphIFS.show_digraph()","pinned":true,"hidden":false,"mode":"ojs"},{"id":978,"value":"From there, I guess it's not too hard to write down the incidence matrix:\n${tex.block`\nM = \\left(\n\\begin{array}{cccccc}\n 0 & 0 & 0 & 0 & 0 & 1 \\\\\n 1 & 0 & 0 & 0 & 0 & 0 \\\\\n 0 & 2 & 1 & 0 & 0 & 0 \\\\\n 0 & 0 & 1 & 0 & 0 & 0 \\\\\n 0 & 0 & 0 & 1 & 0 & 0 \\\\\n 0 & 0 & 0 & 0 & 2 & 1 \\\\\n\\end{array}\n\\right)`}\nNow, the characteristic polynomial of ${tex`M`} is\n${tex.block`p(\\lambda) = \\lambda ^6-2 \\lambda ^5+\\lambda ^4-4 = (\\lambda +1) \\left(\\lambda ^2-2 \\lambda +2\\right) \\left(\\lambda ^3-\\lambda ^2-2\\right).`}\nThus, the dimension should be ${tex`\\log(\\lambda)/\\log(\\sqrt{2}),`} where ${tex`\\lambda`} is the largest positive root of ${tex`\\lambda ^3-\\lambda ^2-2`}. Since this is a cubic, we can use [Cardano's formula](https://en.wikipedia.org/wiki/Cubic_equation#Cardano's_formula) to find its roots. Doing so, we find that the dimension is exactly:\n${tex.block`\\frac{\\log \\left(\\frac{1}{3} \\left(1+\\sqrt[3]{28-3 \\sqrt{87}}+\\sqrt[3]{28+3\n \\sqrt{87}}\\right)\\right)}{\\log \\left(\\sqrt{2}\\right)}.`}","pinned":false,"hidden":false,"mode":"md"},{"id":1000,"value":"Of course, maybe the biggest deal is that we can generate an image of the boundary:","pinned":false,"hidden":false,"mode":"md"},{"id":926,"value":"digraphIFS.render_stochastic({\n image_width: width < 500 ? width : 500,\n n: 100000,\n colors: true,\n color_depth: 4\n})[6]","pinned":true,"hidden":false,"mode":"ojs"},{"id":1094,"value":"## Ancillary Code","pinned":false,"hidden":false,"mode":"md"},{"id":707,"value":"f_invs = fs.map((af) => af.invert())","pinned":true,"hidden":false,"mode":"ojs"},{"id":599,"value":"IFS = new IteratedFunctionSystem(fs)","pinned":true,"hidden":false,"mode":"ojs"},{"id":826,"value":"F = [\n [1, 0],\n [1, 1],\n [0, 1],\n [-1, 0],\n [-1, -1],\n [0, -1]\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":832,"value":"fs = D.map((d) => new AffineFunction([AInv, math.multiply(AInv, d)]))","pinned":true,"hidden":false,"mode":"ojs"},{"id":822,"value":"D = [\n [0, 0],\n [1, 0]\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":824,"value":"AInv = math.inv(A)","pinned":true,"hidden":false,"mode":"ojs"},{"id":819,"value":"A = [\n [1, 1],\n [-1, 1]\n]","pinned":true,"hidden":false,"mode":"ojs"},{"id":1005,"value":"// Used for pre-generated images:\n//\n// attractor = IFS.deterministic_path_approximation({\n// init: [\n// [0, 0],\n// [1, -1],\n// [2, 0],\n// [1, 1]\n// ],\n// max_depth: 15\n// }).flat(1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":498,"value":"## Imports","pinned":false,"hidden":false,"mode":"md"},{"id":2,"value":"import {\n IteratedFunctionSystem,\n AffineFunction,\n shift,\n scale,\n rotate,\n degree\n} from \"@mcmcclur/iteratedfunctionsystem-class\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":529,"value":"import { DigraphIFS } from \"@mcmcclur/digraphifs-class\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":538,"value":"math = require(\"mathjs\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}