31:Ta7a,IteratedFunctionSystem = { let IteratedFunctionSystem = class IteratedFunctionSystem { constructor(affine_lists) { this.affine_lists = affine_lists || []; this.length = this.affine_lists.length; this.affine_function_list = this.affine_lists.map(function (Ab) { return new AffineFunction(Ab); }); this.function_list = this.affine_function_list.map(function (f) { return f.f; }); this.are_similarities = this.affine_function_list.every(function (Ab) { return Ab.is_similarity; }); this.norms = this.affine_function_list.map(function (Ab) { return Ab.norm; }); this.is_contractive = this.norms.every(function (x) { return x < 1; }); if (this.is_contractive) { let s = dimension(this.norms); this.dimension = s; this.plist = this.norms.map(function (r) { return Math.pow(r, s); }); } } }; IteratedFunctionSystem.prototype.stochastic_point_approximation = stochastic_point_approximation; IteratedFunctionSystem.prototype.render_stochastic = function (opts = {}) { opts.length = this.length; let pic_with_scales = point_plot( this.stochastic_point_approximation(opts), opts ); this.xScale = pic_with_scales.xScale; this.yScale = pic_with_scales.yScale; return pic_with_scales.canvas; }; IteratedFunctionSystem.prototype.deterministic_path_approximation = deterministic_path_approximation; IteratedFunctionSystem.prototype.render_deterministic = function (opts = {}) { if (opts.colors && !opts.fill_colors && !opts.stroke_colors) { opts.fill_colors = opts.colors; opts.stroke_colors = opts.colors; } let pic_with_scales; if (opts.init && opts.init.length == 1) { pic_with_scales = point_plot( this.deterministic_path_approximation(opts), opts ); } else if (!opts.init) { opts.init = [[0, 0]]; pic_with_scales = point_plot( this.deterministic_path_approximation(opts), opts ); } else { pic_with_scales = path_plot( this.deterministic_path_approximation(opts), opts ); } this.xScale = pic_with_scales.xScale; this.yScale = pic_with_scales.yScale; return pic_with_scales.canvas; }; IteratedFunctionSystem.prototype.iterate = function (n) { let afs = this.affine_function_list; let new_afs = [rotate(0)]; for (let i = 0; i < n; i++) { new_afs = new_afs.map((naf) => afs.map((af) => naf.compose(af))).flat(); } return new IteratedFunctionSystem(new_afs); }; return IteratedFunctionSystem; }32:T579,function stochastic_point_approximation(opts = {}) { let { n = 10000, plist = 'auto' } = opts; if (plist == 'auto') { plist = this.plist; } let sum = 0; let accumulated_plist = plist.map(function(x) { let temp = sum + x; sum = temp; return sum; }); accumulated_plist = accumulated_plist.map(function(x) { return x / sum; }); let x = 0; let y = 0; for (let k = 0; k < 10; k++) { let rand = Math.random(); let i = accumulated_plist.filter(function(x) { return x < rand; }).length; let f = this.function_list[i]; let pt = f([x, y]); x = pt[0]; y = pt[1]; } let xmin = x, xmax = x, ymin = y, ymax = y; let pts = new Array(this.length); for (let i = 0; i < this.length; i++) { pts[i] = []; } for (let k = 0; k < n; k++) { let rand = Math.random(); let i = accumulated_plist.filter(function(x) { return x < rand; }).length; let f = this.function_list[i]; let pt = f([x, y]); x = pt[0]; y = pt[1]; if (x < xmin) { xmin = x; } if (x > xmax) { xmax = x; } if (y < ymin) { ymin = y; } if (y > ymax) { ymax = y; } pts[i].push([x, y]); } this.extent = [[xmin, xmax], [ymin, ymax]]; if (opts.extent) { pts.extent = opts.extent; } else { pts.extent = [[xmin, xmax], [ymin, ymax]]; } return pts; }33:Tced,function deterministic_path_approximation(opts = {}) { let { init = [[0, 0]], max_depth = 0, tolerance = 0 } = opts; // With a max_depth of zero (or a tolerance of 1), the default generates just // the initial approimation. // If max_depth == 0 || tolerance == 1, compute the extent on just the init // and return the init. if (max_depth == 0 || tolerance == 1) { let xs = init.map(function (pt) { return pt[0]; }); let xmin = Math.min(...xs); let xmax = Math.max(...xs); let ys = init.map(function (pt) { return pt[1]; }); let ymin = Math.min(...ys); let ymax = Math.max(...ys); this.extent = [ [xmin, xmax], [ymin, ymax] ]; let result = [[init]]; if (opts.extent) { result.extent = opts.extent; } else { result.extent = [ [xmin, xmax], [ymin, ymax] ]; } return result; } // We'll sort the points that we generate into bins; // one for each function in the IFS representing one // part of the self-similar set. let sorted_pts = new Array(this.length); for (let i = 0; i < this.length; i++) { sorted_pts[i] = []; } // We'll build something like a tree construction consisting of the following nodes. let IFS_Node = function (af, norm, depth) { return { af: af, norm: norm, depth: depth, children: "empty" }; }; // Not quite a classic tree construction with a single root; rather, we start // a branch for each function in the IFS to make it easy to color the parts. for (let i = 0; i < this.length; i++) { let af = this.affine_function_list[i]; let norm = this.norms[i]; let root = new IFS_Node(af, norm, 1); let stack = [root]; while (stack.length > 0) { let node = stack.pop(); let children = []; if (node.norm > tolerance && node.depth < max_depth) { for (let j = 0; j < this.length; j++) { let child_af = node.af.compose(this.affine_function_list[j]); let norm = node.norm * this.norms[j]; let depth = node.depth + 1; let child = new IFS_Node(child_af, norm, depth); children.push(child); stack.push(child); } node.children = children; } else { sorted_pts[i].push(init.map(node.af.f)); } } } // Compute the extent based on the points. let all_pts = sorted_pts .reduce(function (x, y) { return x.concat(y); }) .reduce(function (x, y) { return x.concat(y); }); let x_values = all_pts.map(function (a) { return a[0]; }); let xmin = Math.min(...x_values); let xmax = Math.max(...x_values); let y_values = all_pts.map(function (a) { return a[1]; }); let ymin = Math.min(...y_values); let ymax = Math.max(...y_values); this.extent = [ [xmin, xmax], [ymin, ymax] ]; if (opts.extent) { sorted_pts.extent = opts.extent; } else { sorted_pts.extent = [ [xmin, xmax], [ymin, ymax] ]; } // If the init has length one, we'll need to return a form that's // appropriate for point_plot. if (init.length == 1) { let extent = sorted_pts.extent; sorted_pts = sorted_pts.map((a) => a.map((o) => o.flat())); sorted_pts.extent = extent; } return sorted_pts; }34:T6c7,function point_plot(pts_in, options = {}) { if (!options.extent) { options.extent = pts_in.extent; } let computed_options = set_graphic_option_parameters(options); let image_width = computed_options[0]; let image_height = computed_options[1]; let xScale = computed_options[2]; let yScale = computed_options[3]; let rScale = computed_options[4]; let colors = computed_options[5]; // let colors; // if (computed_options[7]) { // colors = computed_options[7]; // } else { // colors = computed_options[5]; // } let d3Canvas = d3.create("canvas"); let canvas = d3Canvas.node(); let context = canvas.getContext("2d"); d3Canvas.attr("width", image_width).attr("height", image_height); // If called on paths generated by IFS.deterministic_path_approximation, // we should flatten it one level. let pts = pts_in; // if (pts_in[0][0][0].constructor === Array) { // pts = []; // for (let i = 0; i < options.length; i++) { // pts[i] = []; // for (let j = 0; j < pts_in[i].length; j++) { // pts[i][j] = pts_in[i][j].reduce(function (a, b) { // return a.concat(b); // }); // } // } // } else { // pts = pts_in; // } function drawPoint(point) { context.moveTo(xScale(point[0]) + 1, yScale(point[1])); context.arc(xScale(point[0]), yScale(point[1]), 1, 0, 2 * Math.PI); } for (let i = 0; i < pts.length; i++) { context.beginPath(); pts[i].forEach(drawPoint); context.fillStyle = colors[i % colors.length]; context.fill(); } if (options.axes) { draw_axes(context, options.extent, xScale, yScale, options.axes); } return { canvas: canvas, xScale: xScale, yScale: yScale }; }35:T9cb,function path_plot(paths, options = {}) { if (!options.extent) { options.extent = paths.extent; } if (!options.init) { options.init = [[0, 0]]; } if (options.init.length == 1) { options.show_vertices = true; } let computed_options = set_graphic_option_parameters(options); let image_width, image_height, xScale, yScale, rScale, fill_colors, stroke_colors; image_width = computed_options[0]; image_height = computed_options[1]; xScale = computed_options[2]; yScale = computed_options[3]; rScale = computed_options[4]; fill_colors = computed_options[5]; stroke_colors = computed_options[6]; let d3Canvas = d3.create("canvas"); let canvas = d3Canvas.node(); let context = canvas.getContext("2d"); d3Canvas.attr("width", image_width).attr("height", image_height); function drawPath(path, i) { context.beginPath(); path.forEach(function (pt, index) { if (index == 0) { context.moveTo(xScale(pt[0]), yScale(pt[1])); } else { context.lineTo(xScale(pt[0]), yScale(pt[1])); } }); context.closePath(); if (fill_colors && fill_colors != "none") { context.fillStyle = fill_colors[i % fill_colors.length]; context.fill(); } let stroke = false; if (stroke_colors && stroke_colors != "none") { stroke = true; context.strokeStyle = stroke_colors[i % stroke_colors.length]; } if (options.lineWidth) { stroke = true; context.lineWidth = options.lineWidth; } if (stroke) { context.stroke(); } context.closePath(); } for (let i = 0; i < paths.length; i++) { for (let j = 0; j < paths[i].length; j++) { drawPath(paths[i][j], i); } } function drawPoint(point, r) { context.beginPath(); context.moveTo(xScale(point[0]) + 1, yScale(point[1])); context.arc(xScale(point[0]), yScale(point[1]), r, 0, 2 * Math.PI); context.fillStyle = "black"; // colors[i % colors.length]; context.fill(); context.closePath(); } if (options.show_vertices) { let r = options.vertex_size || 2; for (let i = 0; i < paths.length; i++) { for (let j = 0; j < paths[i].length; j++) { for (let k = 0; k < paths[i][j].length; k++) { drawPoint(paths[i][j][k], r); } } } } if (options.axes) { draw_axes(context, options.extent, xScale, yScale, options.axes); } return { canvas: canvas, xScale: xScale, yScale: yScale }; }36:T588,function draw_axes(context, extent, xScale, yScale, axes = {}) { let xmin = extent[0][0]; let xmax = extent[0][1]; let ymin = extent[1][0]; let ymax = extent[1][1]; let { origin = [0, 0], font = '12px Times' } = axes; let [x0, y0] = origin; context.strokeStyle = 'black'; context.beginPath(); context.moveTo(xScale(xmin), yScale(y0)); context.lineTo(xScale(xmax), yScale(y0)); context.stroke(); context.beginPath(); context.moveTo(xScale(x0), yScale(ymin)); context.lineTo(xScale(x0), yScale(ymax)); context.stroke(); let xrange = xmax - xmin; let yrange = ymax - ymin; let xticks = d3.ticks(xmin, xmax, 5); // .filter(function(x) { // return x != 0; // }); let yticks = d3.ticks(ymin, ymax, 5); // .filter(function(x) { // return x != 0; // }); context.fillStyle = 'black'; context.font = font; xticks.forEach(function(x) { context.beginPath(); context.moveTo(xScale(x), yScale(y0)); context.lineTo(xScale(x), yScale(y0 + yrange / 50)); context.stroke(); context.fillText( x, xScale(x - (xmax - xmin) / 100), yScale(y0 - 0.04 * yrange) ); }); yticks.forEach(function(y) { context.beginPath(); context.moveTo(xScale(x0), yScale(y)); context.lineTo(xScale(x0 - xrange / 50), yScale(y)); context.stroke(); context.fillText(y, xScale(x0 + 0.02 * xrange), yScale(y - yrange / 200)); }); }37:Td6d,function set_graphic_option_parameters( options = { /* Must include extent */ } ) { let extent = options.extent; let { image_width = 500, image_height = 0.625 * image_width } = options; let xmin, xmax, ymin, ymax; xmin = extent[0][0]; xmax = extent[0][1]; ymin = extent[1][0]; ymax = extent[1][1]; let internal_padding = 0; let xrange = xmax - xmin; xmin = xmin - internal_padding * xrange; xmax = xmax + internal_padding * xrange; xrange = xmax - xmin; let yrange = ymax - ymin; ymin = ymin - internal_padding * yrange; ymax = ymax + internal_padding * yrange; yrange = ymax - ymin; let xmid = (xmax + xmin) / 2; let ymid = (ymax + ymin) / 2; if (xrange * image_height > yrange * image_width) { let delta = xrange / image_width; ymin = ymid - (image_height * delta) / 2; ymax = ymid + (image_height * delta) / 2; // yrange = ymax-ymin; } else if (xrange * image_height <= yrange * image_width) { let delta = yrange / image_height; xmin = xmid - (image_width * delta) / 2; xmax = xmid + (image_width * delta) / 2; // xrange = xmax-xmin; } let external_padding; if (options.padding === 0) { external_padding = 0; } else if (!options.padding) { external_padding = 10; } else { external_padding = options.padding; } let xScale = d3 .scaleLinear() .domain([xmin, xmax]) .range([external_padding, image_width - external_padding]); let yScale = d3 .scaleLinear() .domain([ymin, ymax]) .range([image_height - external_padding, external_padding]); let rScale = d3 .scaleLinear() .domain([0, xmax - xmin]) .range([0, image_width - external_padding]); let fill_colors, colors; if (options.colors) { options.fill_colors = options.colors; colors = []; for (let i = 0; i < 20; i++) { colors.push(d3.schemeCategory10[i % 10]); } } if (options.fill_colors && options.fill_colors.constructor === Array) { fill_colors = options.fill_colors; } else if (!options.fill_colors) { fill_colors = ["black"]; } else if (options.fill_colors == "auto") { fill_colors = []; for (let i = 0; i < 20; i++) { fill_colors.push(d3.schemeCategory10[i % 10]); } } else if ( options.fill_colors && typeof options.fill_colors == "string" && options.fill_colors != "none" ) { fill_colors = [options.fill_colors]; } else if (options.fill_colors == "none") { fill_colors = "none"; } else if (options.fill_colors) { fill_colors = []; for (let i = 0; i < 20; i++) { fill_colors.push(d3.schemeCategory10[i % 10]); } } let stroke_colors; if (options.stroke_colors && options.stroke_colors.constructor === Array) { stroke_colors = options.stroke_colors; } else if (!options.stroke_colors) { stroke_colors = ["black"]; } else if (options.stroke_colors == "auto") { stroke_colors = []; for (let i = 0; i < 20; i++) { stroke_colors.push(d3.schemeCategory10[i % 10]); } } else if (options.stroke_colors == "match") { stroke_colors = fill_colors; } else if ( options.stroke_colors && typeof options.stroke_colors == "string" && options.stroke_colors != "none" ) { stroke_colors = [options.stroke_colors]; } else { stroke_colors = "none"; } return [ image_width, image_height, xScale, yScale, rScale, fill_colors, stroke_colors ]; }38:[] 2f:{"title":"IteratedFunctionSystem Class","cells":[{"id":0,"value":"# IteratedFunctionSystem Class\n\nThis notebook implements an `IteratedFunctionSystem` class and provides some basic reference, assuming some knowledge of IFSs. For an introduction to iterated function systems and tutorial on how to use the tools in this notebook, see my [Iterated Function Systems notebook](https://observablehq.com/@mcmcclur/iterated-function-systems).","pinned":false,"hidden":false,"mode":"md"},{"id":587,"value":"## Basic introduction\n\nIterated function systems are defined as lists of contractive `AffineFunction` objects, which we can import from my [AffineFunction class notebook](https://observablehq.com/@mcmcclur/affinefunction-class). That notebook also defines several utilities to facilitate the construction of `AffineFunction`s, like the `scale` function:","pinned":false,"hidden":false,"mode":"md"},{"id":596,"value":"import {\n AffineFunction,\n scale,\n rotate,\n reflect,\n shift,\n pi,\n degree\n} from \"@mcmcclur/affinefunction-class\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":610,"value":"The [AffineFunction class notebook](https://observablehq.com/@mcmcclur/affinefunction-class) has more information on `AffineFunction`s.\n\nWith those in hand, we can define an IFS for the Sierpinski triangle:","pinned":false,"hidden":false,"mode":"md"},{"id":607,"value":"IFS = new IteratedFunctionSystem([\n scale(1 / 2),\n scale(1 / 2, [1, 0]),\n scale(1 / 2, [1 / 2, Math.sqrt(3) / 2])\n])","pinned":true,"hidden":false,"mode":"ojs"},{"id":617,"value":"As the Observable inspector indicates, an `IteratedFunctionSystem` object has several (potentially interesting) properties and methods associated with it. Of immediate interest are the two renderers\n\n * `IFS.render_deterministic`, which renders an image using a deterministic algorithm and\n * `IFS.render_stochastic` which renders an image using a stochastic (or random) algorithm.\n\nHere's the result of the simplest call to `IFS.render_stochastic`:","pinned":false,"hidden":false,"mode":"md"},{"id":625,"value":"IFS.render_stochastic()","pinned":true,"hidden":false,"mode":"ojs"},{"id":641,"value":"And here's the result of `IFS.render_deterministic` using several options:","pinned":false,"hidden":false,"mode":"md"},{"id":568,"value":"IFS.render_deterministic({\n max_depth: 7,\n colors: true,\n axes: true\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":646,"value":"### More on `IFS.render_stochastic`\n\n`IFS.render_stochastic` accepts the following options:\n\n * Computational options:\n * `n`: The number of points to generate; defaults to 10000.\n * `plist`: Probabilities to use when running the algorithm.\n * Graphics options:\n * `extent`: A list of the form `[[xmin,xmax], [ymin,ymax]]` defining the plot region in the xy-plane. By default, this is automatically computed to include the whole image.\n * `colors`: The default color is `'black'` but you can color the self-similar pieces by specifying\n * A list of valid CSS colors,\n * A single CSS color for the whole image,\n * `'auto'` or `true` for `d3.schemeCategory10` colors.\n * `axes`: A Boolean indicating whether to draw axes or not\n * `image_width`: The width of the image\n * `image_height`: The height of the image\n\nWith the exception of `plist`, these are all pretty straightforward. Here's an example for the rest:","pinned":false,"hidden":false,"mode":"md"},{"id":638,"value":"IFS.render_stochastic({\n image_width: 500,\n image_height: 500,\n n: 1500,\n extent: [\n [-1, 1],\n [-1, 1]\n ],\n axes: true,\n colors: true\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1037,"value":"The `plist` option should be a list of non-negative numbers that sum to 1. This weights the functions in the IFS affecting the distribution of points in the approximation. By default, they are chosen in an attempt to distribute the points uniformly throughout the set. You can specify other values to get other types of distributions.","pinned":false,"hidden":false,"mode":"md"},{"id":728,"value":"IFS.render_stochastic({\n image_width: 500,\n image_height: 500,\n n: 10000,\n plist: [0.2, 0.2, 0.6]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1044,"value":"The IFS knows values that should generate a uniform distribution of points.","pinned":false,"hidden":false,"mode":"md"},{"id":1042,"value":"IFS.plist","pinned":true,"hidden":false,"mode":"ojs"},{"id":748,"value":"### More on `IFS.render_deterministic`\n\nIn addition to the same graphics options accepted by `IFS.render_stochastic`, the `IFS.render_deterministic` function accepts the following computational options:\n\n * Computational options:\n * `init`: A list of `[x,y]` points indicating the initial approximation to the set. By default, this is `[[0,0]]` resulting in a point approximation to the fractal.\n * `max_depth`: The maximum depth of the iteration in the approximation\n * `tolerance`: A cutoff based on the minimum norm required to generate the approximation.\n\nIn addition, there are a few additional types of graphics options:\n * Additional graphics options\n * `fill_colors` and `stroke_colors`: Since the approximation is generally a collection of polygons, you can specify the fill and stroke of those polygons separately. You can specify both by just using `colors`.\n * `show_vertices`: A Boolean indicating whether we should show the vertices or not.","pinned":false,"hidden":false,"mode":"md"},{"id":765,"value":"IFS.render_deterministic({\n max_depth: 4,\n init: [\n [0, 0],\n [1, 0],\n [1 / 2, Math.sqrt(3) / 2]\n ],\n fill_colors: true,\n show_vertices: true,\n image_width: 640,\n image_heigth: 400\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1063,"value":"### Other properties\n\nAn iterated function system knows some things about itself, like its `dimension` (already mentioned) `plist`.","pinned":true,"hidden":false,"mode":"md"},{"id":564,"value":"md`## Implementation`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":85,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":80,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":76,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":285,"value":"$35","pinned":true,"hidden":false,"mode":"ojs"},{"id":179,"value":"$36","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"function dimension(norms) {\n function numerator(s) {\n return (\n norms.reduce(function(x, y) {\n return x + Math.pow(y, s);\n }, 0) - 1\n );\n }\n function denominator(s) {\n return norms.reduce(function(x, y) {\n return x + Math.pow(y, s) * Math.log(y);\n }, 0);\n }\n function newton_step(s) {\n return s - numerator(s) / denominator(s);\n }\n let s = 1;\n for (let i = 0; i < 5; i++) {\n s = newton_step(s);\n }\n return s;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"$37","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1","titling":"auto"}