I'm a professor of mathematics at the University of North Carolina Asheville. I've also done a fair amount of consulting work over the years focusing on scientific and data visualization.
I'm happy to be part of the first Observable Ambassador's cohort.
IFS QuickstartIterated Function SystemsConstruction of the Serpinski triangleThe Sierpinski pedal triangleSimilarity and the Pedal TriangleDeterministic IFS algorithmsSelf-similar spiralsStochastic IFS algorithmsGeneralized Sierpinski trianglesThe Z-CurvePoly-gasketsThe Koch snowflakeBarnsley's fernAffineFunction ClassSimilarity transformationsThe TwindragonBox-counting dimension examplesMcMullen carpetsThe Twindragon (with boundary)Self-affine tilesTutorial on self-affine tilesA self-affine tile with holesSelf-affine tiles via polygon mergeThe Eisenstein fractionsGolden rectangle fractalsDeterministic digraph IFS algorithmsA stochastic digraph IFS algorithmMixed self-similarityFractalized squareHilbert's coordinate functionsRauzy Fractals
IteratedFunctionSystem Class
import {
AffineFunction,
scale,
rotate,
reflect,
shift,
pi,
degree
} from "@mcmcclur/affinefunction-class"
IFS = new IteratedFunctionSystem([
scale(1 / 2),
scale(1 / 2, [1, 0]),
scale(1 / 2, [1 / 2, Math.sqrt(3) / 2])
])
IFS.render_stochastic()
IFS.render_deterministic({
max_depth: 7,
colors: true,
axes: true
})
IFS.render_stochastic({
image_width: 500,
image_height: 500,
n: 1500,
extent: [
[-1, 1],
[-1, 1]
],
axes: true,
colors: true
})
IFS.render_stochastic({
image_width: 500,
image_height: 500,
n: 10000,
plist: [0.2, 0.2, 0.6]
})
IFS.plist
IFS.render_deterministic({
max_depth: 4,
init: [
[0, 0],
[1, 0],
[1 / 2, Math.sqrt(3) / 2]
],
fill_colors: true,
show_vertices: true,
image_width: 640,
image_heigth: 400
})
Other properties
An iterated function system knows some things about itself, like its dimension (already mentioned) plist.
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;
}
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;
}
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;
}
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
};
}
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
};
}
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));
});
}
function dimension(norms) {
function numerator(s) {
return (
norms.reduce(function(x, y) {
return x + Math.pow(y, s);
}, 0) - 1
);
}
function denominator(s) {
return norms.reduce(function(x, y) {
return x + Math.pow(y, s) * Math.log(y);
}, 0);
}
function newton_step(s) {
return s - numerator(s) / denominator(s);
}
let s = 1;
for (let i = 0; i < 5; i++) {
s = newton_step(s);
}
return s;
}
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
];
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
