Nonrecursive fractal

A Koch snowflake.
CC-BY-SA Wikimedia Commons

While thinking about the Koch snowflake it occurred to me that a recursive algorithm to generate one side of the curve would be trivial, but a non-recursive algorithm is pretty simple as well, although it took a lot of thought on my part to get it to work. I don't claim to be an expert at algorithms but I'm pleased when I can figure something out. Here's what I came up with.

Your browser does not support the HTML5 canvas tag.

Fractal order: 0 (click the arrows)

The idea is to start out with the smallest generator unit, calculating its size by scaling per the length of the parent segments, and accumulating the rotation angles. Then draw the generator unit at that scale and rotation. Repeat for the total number of smallest generator units, which would be the number of segments in the unit to the power of (fractal order − 1).

Here's the code including the graphics scaling.

// display initialization and scaling

var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
var xs = 600.0, xo = 0.0, ys = -600.0, yo = 300.0;
function x(xv) { return xv*xs + xo; }
function y(yv) { return yv*ys + yo; }

// fractal unit generator

var unit = {
 len:[1, 1, 1, 1],
 angle:[0, 60.0, -60.0, 0]

// initialize

var fractal_order = 1;
var max_fractal_order = 8;
var unit_segs = unit.len.length,
 scl, rot = 0.0,
 px, py,
 segcount = Array();
for (var j = 0; j < max_fractal_order; ++j)

// get size of the unit if not equal to 1

for (var j = 0, px = 0, py = 0; j < unit_segs; ++j) {
 unit.angle[j] *= rad;
 px += unit.len[j] * Math.cos(unit.angle[j]);
 py += unit.len[j] * Math.sin(unit.angle[j]);
var unitsize = Math.sqrt(px*px + py*py);
for (var j = 0; j < unit_segs; ++j) unit.len[j] /= unitsize;

// draw

function drawit() {
 var iterations = Math.pow(unit_segs, fractal_order-1);
 var k;
 px = 0.0; py = 0.0;
 ctx.moveTo(x(px), y(py));
 for (var i = 0; i < iterations; ++i) {
  scl = 1.0;
  rot = 0.0;
  for (k = 0; k < fractal_order-1; ++k) {
   scl *= unit.len[segcount[k]];
   rot += unit.angle[segcount[k]];
  for (var j = 0; j < unit_segs; ++j) {
   px += scl * unit.len[j] * Math.cos(unit.angle[j]+rot);
   py += scl * unit.len[j] * Math.sin(unit.angle[j]+rot);
   ctx.lineTo(x(px), y(py));
   k = fractal_order-1;
   while (k >= 0 && ++segcount[k] >= unit_segs)
    segcount[k--] = 0;

Granted, this isn't particularly useful for anything. It's far simpler to use a recursive algorithm. But given that I did spend a fair amount of time figuring this out, I may as well write about it. I suspect the recursive version may have a bit more overhead.

It's kind of a retro-modern thing, to write an algorithm in the spirit of those olden days when we didn't have computer languages supporting recursion (think FORTRAN or BASIC from the 1970s), but writing it in a modern language that does.


Popular posts from this blog

The water rocket: Thrust from water

Most probable array of D&D ability scores

The water rocket: Launch tube thrust