2d:null 2e:["$","title",null,{"children":"Box-counting dimension examples | Mark McClure | Observable"}] 33:Tc9c,({ "Line segment": md`A line segment should clearly have dimension 1. My computer yields an estimate of ${tex`1.025`}.`, Squiggle: md`Any smooth curve should have dimension 1. For this one, my computer yields an estimate of ${tex`1.066`}.`, "Solid circle": md`Any set in the plane with postive area should have dimension ${tex`2`}. My compute yields an estimate of ${tex`1.856`} for this solid circle - the most disappointing example on this list.`, "Koch curve": md`The Koch curve is a self similar set consisting of four pieces each scaled by the factor ${tex`1/2`}. Thus, we know its fractal dimension is ${tex.block`\frac{\log 4}{\log 3} \approx 1.26186.`} My computer estimates the dimension to be approximately ${tex`1.248`}, which isn't too bad!`, "Sierpinski triangle": md`The Sierpinski triangle is a self similar set consisting of 3 pieces each scaled by the factor 1/2. Thus, we know its fractal dimension is ${tex.block`\frac{\log 3}{\log 2} \approx 1.58496.`} My computer estimates the dimension to be approximately ${tex`1.586`}, which is pretty good!`, "Sparse spiral": md`This sparse spiral consists of two pieces - one scaled by the factor ${tex`0.95`} about the origin and rotated ${tex`15^{\circ}`}; the other scaled by the factor ${tex`0.15`} and shifted to the right. Thus, we know the dimension ${tex`d`} of the set satisfies the equation ${tex.block`0.95^d + 0.15^d = 1,`} which we can solve to find that ${tex`d\approx 1.4052.`} My computer estimates the dimension to be approximately ${tex`1.445`}.`, "Phylo-spiral": md`This second spiral consists of two pieces - one scaled by the factor ${tex`0.99`} about the origin and rotated ${tex`137.5^{\circ}`}; the other scaled by the factor ${tex`0.1`} and shifted to the right. Thus, we know the dimension ${tex`d`} of the set satisfies the equation ${tex.block`0.99^d + 0.1^d = 1,`} which we can solve to find that ${tex`d\approx 1.7569.`} My computer estimates the dimension to be approximately ${tex`1.743`}.`, "Kieswetter's curve": md`Kiesswetter's curve is not strictly self-similar but, rather, self-affine. Nontheless, its box-counting dimension is known to be ${tex`3/2`}. My computer estimates the dimension to be approximately ${tex`1.477`}.`, "Barnsley's fern": md`Barnsley's fern is another self-affine set. I don't know of any theoretically computed, closed form expression for the dimension but my computer estimates the dimension to be approximately ${tex`1.755`}.`, "British coast": md`The fractal dimension of the British coastline was made famous in Mandelbrot's 1967 paper, [How long is the coast of Britain](https://en.wikipedia.org/wiki/How_Long_Is_the_Coast_of_Britain). The data here, extracted from [Natural Earth's physical vectors](https://www.naturalearthdata.com/downloads/10m-physical-vectors/) suggests the answer is about ${tex`1.289`}, which is close to the value suggested by the article.`, Trees: md`This binarized photo of the branches of a stand of trees in the winter was taken from [this Wolfram community post](https://community.wolfram.com/groups/-/m/t/1025046). My computer estimates the dimension to be about ${tex`1.892`}, in close agreement with the computations from the source.` }[example])34:T580,box_plot = { let canvas = fractals.canvas; let w = width < 800 ? width : 800; let h = (w * canvas.height) / canvas.width; let container = d3 .create("div") .style("position", "relative") .style("width", `${w}px`) .style("height", `${h}px`); container .append("div") .style("position", "absolute") .style("top", 0) .style("left", 0) .style("width", `${w}px`) .style("height", `${h}px`) .append("img") .attr("width", w) .attr("height", h) .attr("src", fractals.dataURL); if (n < fractals.cnts.length) { let svg = container .append("svg") .attr("id", "box_container") .style("position", "absolute") .style("top", 0) .style("left", 0) .style("width", `${w}px`) .style("height", `${h}px`) .attr("width", w) .attr("height", h); if (n < fractals.cnts.length - 1) { let s = fractals.cnts[n].s; let boxes = fractals.cnts[n].boxes; svg .selectAll("rect") .data(boxes) .join("rect") .attr("x", (d) => (s * d[1] * w) / canvas.width) .attr("y", (d) => (s * d[0] * h) / canvas.height) .attr("width", (d) => (s * w) / canvas.width) .attr("height", (d) => (s * h) / canvas.height) .attr("opacity", 0.2) .attr("stroke", "white") .attr("stroke-width", 1); } } return container.node(); }35:T5d9,regression_line = { let cnts = fractals.cnts.map((o) => Object.assign({}, o)); cnts.forEach(function (o) { o["log s"] = Math.log(o.s); o["log cnt"] = Math.log(o.cnt); }); let x0 = cnts[0]["log s"]; let x1 = cnts.slice(-1)[0]["log s"]; let aspect = (cnts[0]["log cnt"] - cnts.slice(-1)[0]["log cnt"]) / (cnts.slice(-1)[0]["log s"] - cnts[0]["log s"]); let w = width < 640 ? width : 640; let h = w * aspect; let plot = Plot.plot({ x: { //type: "log" // domain: [0, 1.2], // ticks: [0.25, 0.5, 0.75], // tickFormat: ".2s" }, y: {}, width: w, height: h, padding: 100, marks: [ Plot.dot(cnts, { x: "log s", y: "log cnt", fill: "lightgray", stroke: "black", strokeWidth: 2, title: (d, i) => `(${d.s}, ${d.cnt})` }), Plot.line([ [x0, regression.b], [x1, -regression.m * x1 + regression.b] ]), // Add the axes Plot.ruleX([x0]), Plot.ruleY([cnts.slice(-1)[0]["log cnt"]]) ] }); // Generate a bit of LaTeX. let tex_snippet = MathJax.tex2svg( String.raw`\log N_{\varepsilon} \approx ${d3.format("0.3f")( regression.b )} - ${d3.format("0.3f")(regression.m)}\log \varepsilon` ).querySelector("svg"); // and append it to the image d3.select(plot) .append("g") .attr("transform", `translate(${w * 0.3} ${0.63 * h}) scale(1.2)`) .append(() => tex_snippet); return plot; }36:T4e7,methodology = md`## Methodology If we cover a smooth curve of length ${tex`L`} with squares of side length ${tex`s`} (as is the example picture when the Example menu is set to "Line segment" or "Squiggle"), then we might expect the number of squares ${tex`N_s`} to be related to ${tex`s`} via ${tex.block`N_s s \approx L.`} If the object we are covering is a solid set of dimension two with area ${tex`A`} (as in the "Solid circle" example), then perhaps the relationship should be ${tex.block`N_s s^2 \approx A.`} More generally, if we cover an object of dimension ${tex`d`}, we might expect that ${tex.block`N_s s^d \approx M,`} where ${tex`M`} is some ${tex`d`}-dimensional measure of the size of the object. If we apply the logarithm to both sides, we can rewrite this approximate equation as ${tex.block`\log N_s \approx \log M - d \log s.`} Thus, if we compute box-counts for a sequence of side lengths close to zero, produce a log-log plot of that data, and fit a regression line, then the dimension of the object should appear as the negative slope of the line. You can read more details in this rather total [work in progress](https://www.marksmath.org/classes/Fall2021ChaosAndFractals/chaos_and_fractals_2021/chapter-fractal_dimension.html).`37:T48e,function box_count(canvas) { let ctx = canvas.getContext("2d"); let im_data = ctx.getImageData(0, 0, canvas.width, canvas.height); let cnts = []; for (let s = 1; s <= d3.min([canvas.width, canvas.height]); s = 2 * s) { let boxes = []; let cnt = 0; for (let i = 0; s * (i + 1) <= canvas.height; i++) { for (let j = 0; s * (j + 1) <= canvas.width; j++) { if (check_box(i, j, s)) { cnt = cnt + 1; boxes.push([i, j]); } } } cnts.push({ s: s, cnt: cnt, boxes: boxes }); } function check_box(i, j, s) { for (let i0 = i * s; i0 < (i + 1) * s; i0++) { for (let j0 = j * s; j0 < (j + 1) * s; j0++) { let ij0 = 4 * (j0 + i0 * canvas.width); if ( // im_data.data[ij0] == 0 && // im_data.data[ij0 + 1] == 0 && // im_data.data[ij0 + 2] == 0 && // im_data.data[ij0 + 3] == 255 im_data.data[ij0] < 100 && im_data.data[ij0 + 1] < 100 && im_data.data[ij0 + 2] < 100 && im_data.data[ij0 + 3] > 155 ) { return true; } } } return false; } return cnts; }38:T1653,fractals = { let canvas; if (example == "Sierpinski triangle") { let sierpIFS = new IteratedFunctionSystem([ scale(1 / 2), scale(1 / 2, [1, 0]), scale(1 / 2, [1 / 2, Math.sqrt(3) / 2]) ]); canvas = sierpIFS.render_deterministic({ max_depth: 7, init: [ [0, 0], [1, 0], [1 / 2, Math.sqrt(3) / 2] ], extent: [ [0, 1], [-0.1, 0.9] ], image_width: 512, image_height: 512 }); } else if (example == "Sparse spiral") { let ifs = new IteratedFunctionSystem([ scale(0.95).compose(rotate(15 * degree)), scale(0.15, [1, 0]) ]); canvas = ifs.render_stochastic({ n: 20000, image_width: 1024, image_height: 1024 }); } else if (example == "Phylo-spiral") { let ifs = new IteratedFunctionSystem([ scale(0.99).compose(rotate(137.5 * degree)), scale(0.1, [1, 0]) ]); canvas = ifs.render_stochastic({ n: 100000, image_width: 1024, image_height: 1024 }); } else if (example == "Koch curve") { let f0 = scale(1 / 3, [0, 0]); let f1 = shift([1 / 3, 0]) .compose(scale(1 / 3)) .compose(rotate(Math.PI / 3)); let f2 = shift([1 / 2, Math.sqrt(3) / 6]) .compose(scale(1 / 3)) .compose(rotate(-Math.PI / 3)); let f3 = scale(1 / 3, [1, 0]); canvas = new IteratedFunctionSystem([f0, f1, f2, f3]).render_deterministic({ max_depth: 6, init: [ [0, 0], [1, 0] ], extent: [ [0, 1], [0, 1 / 2] ], image_width: 512, image_height: 256 }); } else if (example == "Kieswetter's curve") { canvas = new IteratedFunctionSystem([ new AffineFunction([ [ [1 / 4, 0], [0, -1 / 2] ], [0, 0] ]), new AffineFunction([ [ [1 / 4, 0], [0, 1 / 2] ], [1 / 4, -1 / 2] ]), new AffineFunction([ [ [1 / 4, 0], [0, 1 / 2] ], [1 / 2, 0] ]), new AffineFunction([ [ [1 / 4, 0], [0, 1 / 2] ], [3 / 4, 1 / 2] ]) ]).render_deterministic({ max_depth: 6, init: [ [0, 0], [1, 1] ], extent: [ [0, 1], [-1, 1] ], image_width: 512, image_height: 1024 }); } else if (example == "Barnsley's fern") { canvas = new IteratedFunctionSystem([ [ [ [0.85, 0.04], [-0.04, 0.85] ], [0, 1.6] ], [ [ [-0.15, 0.28], [0.26, 0.24] ], [0, 0.44] ], [ [ [0.2, -0.26], [0.23, 0.22] ], [0, 1.6] ], [ [ [0, 0], [0, 0.16] ], [0, 0] ] ]).render_stochastic({ n: 80000, image_width: 512, image_height: 1024 }); } else if (example == "Line segment") { canvas = d3.create("canvas").attr("width", 1024).attr("height", 256).node(); let ctx = canvas.getContext("2d"); ctx.beginPath(); ctx.moveTo(20, 200); ctx.lineTo(1000, 20); ctx.lineWidth = 1.5; ctx.stroke(); ctx.closePath(); } else if (example == "Squiggle") { let w = 1024; let h = 512; let xmin = 0; let xmax = 13; let ymin = 0; let ymax = 7; let x_scale = d3.scaleLinear().domain([xmin, xmax]).range([0, w]); let y_scale = d3.scaleLinear().domain([ymin, ymax]).range([h, 0]); canvas = d3.create("canvas").attr("width", w).attr("height", h).node(); let ctx = canvas.getContext("2d"); ctx.beginPath(); ctx.moveTo(x_scale(0), y_scale(0)); for (let t = 0; t <= 2 * Math.PI; t = t + Math.PI / 100) { ctx.lineTo(x_scale(Math.sin(3 * t) + 2 * t), y_scale(t)); } ctx.lineWidth = 1.5; ctx.stroke(); ctx.closePath(); } else if (example == "Solid circle") { canvas = d3.create("canvas").attr("width", 512).attr("height", 512).node(); let ctx = canvas.getContext("2d"); ctx.beginPath(); ctx.arc(250, 255, 200, 0, 2 * Math.PI); ctx.fill(); } else if (example == "British coast") { let pts = british_coast.features[0].geometry.coordinates; let xpts = pts.map((pt) => pt[0]); let xmin = Math.floor(d3.min(xpts)); let xmax = Math.ceil(d3.max(xpts)); let ypts = pts.map((pt) => pt[1]); let ymin = Math.floor(d3.min(ypts)); let ymax = Math.ceil(d3.max(ypts)); let w = 512; let h = (w * (ymax - ymin)) / (xmax - xmin); canvas = d3.create("canvas").attr("width", w).attr("height", h).node(); let x_scale = d3.scaleLinear().domain([xmin, xmax]).range([0, w]); let y_scale = d3.scaleLinear().domain([ymin, ymax]).range([h, 0]); let ctx = canvas.getContext("2d"); ctx.beginPath(); ctx.moveTo(x_scale(xpts[0]), y_scale(ypts[0])); for (let i = 1; i < pts.length; i++) { ctx.lineTo(x_scale(xpts[i]), y_scale(ypts[i])); } ctx.stroke(); ctx.closePath(); } else if (example == "Trees") { let bits = await FileAttachment("tree_bits.txt").text(); bits = bits.split(";").map((s) => s.split("").map((c) => parseInt(c))); let w = bits[0].length; let h = bits.length; canvas = d3.create("canvas").node(); canvas.width = w; canvas.height = h; let ctx = canvas.getContext("2d"); for (let i = 0; i < h; i++) { for (let j = 0; j < w; j++) { if (bits[i][j] == 0) { ctx.rect(j, i, 1, 1); } } } ctx.fill(); } return { canvas: canvas, cnts: box_count(canvas), dataURL: canvas.toDataURL() }; }39:[{"id":"b4cec524ddb0a083e699cec9d13d01589a5b902d34559dad74060d63dda13c5c2e80c12b4509eecafffe2aa6528006a0235aad5c9791c5cd97e89601c1fe89c2","href":"https://static.observableusercontent.com/files/b4cec524ddb0a083e699cec9d13d01589a5b902d34559dad74060d63dda13c5c2e80c12b4509eecafffe2aa6528006a0235aad5c9791c5cd97e89601c1fe89c2","name":"british_coastline.json","type":"application/json","lastModified":1635008876044.273,"size":32918},{"id":"72cf07b3114725b039f204d09517da76dd45c7e0567cec4e508ac148a52a8aaea3442ec0ed7f0a2009009e29d6ac905db66e96a796f33fec5630d75f2e9789cc","href":"https://static.observableusercontent.com/files/72cf07b3114725b039f204d09517da76dd45c7e0567cec4e508ac148a52a8aaea3442ec0ed7f0a2009009e29d6ac905db66e96a796f33fec5630d75f2e9789cc","name":"tree_bits.txt","type":"text/plain","lastModified":1635046442846.253,"size":1399124}] 31:{"id":"b0fcdfd7376c3f79","slug":"box-counting-dimension-examples","title":"Box-counting dimension examples","thumbnail":"2cac66ce9b79c89fd0459101d2200affbab875c4a06a3c0703d388dce8b639d1","access_level":"public","create_time":"$D2021-10-23T09:49:09.611Z","update_time":"$D2023-12-04T20:06:54.498Z","view_time":null,"first_public_time":"$D2021-10-25T13:21:53.599Z","has_unpublished_edits":null,"fork":false,"stars":10,"starred":false,"owner":{"type":"team","id":"d771c8ae812d5130","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":"starter_2024"},"version":813,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c3301e515dd08a41","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":null}],"members":[{"type":"individual","id":"c3301e515dd08a41","login":"mcmcclur","name":"Mark McClure","avatar_url":"https://avatars-next.observableusercontent.com/e615e819ce83d43faef607e48c53c5ff63943aa0ba9f5848499bd02fef7396f4","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"bc474ee78311ea3c","slug":"fractals","title":"Fractals","owner":{"id":"d771c8ae812d5130","login":"mcmcclur","name":"Mark McClure"}},"type":"notebook","body":{"title":"Box-counting dimension examples","cells":[{"id":0,"value":"# Box-counting dimension examples\n\nThis notebook implements a box-counting technique to compute fractal dimension and illustrates several examples accessible through the \"Examples\". You can read more about the box-counting technique in the [Methodology section](#methodology).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"viewof example = Inputs.select(\n [\n \"Line segment\",\n \"Squiggle\",\n \"Solid circle\",\n \"Koch curve\",\n \"Sierpinski triangle\",\n \"Sparse spiral\",\n \"Phylo-spiral\",\n \"Kieswetter's curve\",\n \"Barnsley's fern\",\n \"British coast\",\n \"Trees\"\n ],\n {\n value: \"British coast\",\n label: \"Example:\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":755,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":657,"value":"n < fractals.cnts.length - 1\n ? md`The image below illustrates a box covering with ${tex`${fractals.cnts[n].cnt}`} boxes of side length ${tex`${fractals.cnts[n].s}`} pixels. ${\n example == \"Line segment\"\n ? \"You can use the slider to change the side length and, therefore, the box-count.\"\n : \"\"\n }`\n : md`The image below displays just a picture of the set; you can use the slider to visualize box-counts.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":695,"value":"viewof n = {\n let n = Inputs.range([1, fractals.cnts.length - 1], {\n step: 1,\n label: \"Side length:\"\n });\n d3.select(n).select('input[type=\"number\"]').style(\"display\", \"none\");\n // d3.select(n).select(\"label\").style(\"width\", \"20px\");\n\n return n;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":749,"value":"md`\nThe box-count data for this set is:\n\n \n ${fractals.cnts.map((o) => ``)}\n \n \n ${fractals.cnts.map((o) => ``)}\n \n

${tex`s`}	${o.s}
${tex`N_s`}	${o.cnt}

\nyielding a fractal dimension estimate of approximately ${d3.format(\"0.3f\")(\n regression.m\n)}. The regression line is ${tex.block`\\log N_s \\approx ${d3.format(\"0.3f\")(\n regression.b\n)} - ${d3.format(\"0.3f\")(regression.m)} \\log s,`}\nwhich looks like so:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":544,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":713,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":548,"value":"## Code","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"regression = ss.linearRegression(\n fractals.cnts.map((o) => [-Math.log(o.s), Math.log(o.cnt)])\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":291,"value":"british_coast = {\n let map_file = await FileAttachment(\"british_coastline.json\").json();\n let coast = topojson.feature(map_file, map_file.objects.ne_10m_coastline);\n return coast;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":563,"value":"## Imports","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"ss = require(\"simple-statistics\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"topojson = require(\"topojson-client@3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":587,"value":"MathJax = require(\"https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js\").catch(\n () => window[\"MathJax\"]\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 32:"$31:body"