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,
 rad=0.01745329251994329576923690768489,
 segcount = Array();
for (var j = 0; j < max_fractal_order; ++j)
 segcount.push(0);

// 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.beginPath();
 ctx.clearRect(0,0,c.width,c.height);
 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;
  }
 }
 ctx.stroke();
}

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.

Comments

Post a Comment

Popular posts from this blog

Syncing Office 365 Outlook to Google calendar using Power Automate

Image
When my employer switched over from the Google office suite to Microsoft's Office 365, it caused unexpected disruption in my family. I had been sharing my work calendar with my wife (sharing no details, just busy times). It became an integral part of her calendar, to help her coordinate (between her job and my job) who picks up and drops off my son from school, and to let her know when I was free to take a phone call during my work day. Since the switchover to O365, my ability to share a calendar externally was eliminated. Based on documentation I could find, it should be possible, but the option doesn't appear in my employer's implementation of Outlook. I can view my personal Google calendar in my work Outlook calendar, but I can't share it the other way. Microsoft's Power Automate provides a way to solve this problem. It lets you create flows of data, triggered manually or automatically by events, to move data around, not only among the Microsoft products but ...
Read more

Whose hands are biggest? You may be surprised.

Image
A recent project to create an ergonomic handle for 3D printing led me down a path that introduced me to anthropometric measurements of the human hand, which in turn revealed some interesting facts about hand sizes. I had no idea that hand size is dependent on nationality, but I found a number of research articles on this topic. For those who don't want to read further, the answer to the title question is: Based on the data found, Filipino males have the biggest hands, by a significant margin. In fact, the margin is large enough that this population may be considered an outlier from the general human population with respect to hand size. Even Filipina females have larger hands than most males of other nationalities. On the other end of the spectrum, Vietnamese females and Indian females have the smallest hands. Now you can read on for the whole story, or you can skip down to the chart at the end. Idea for a toy My unintentional investigation into hand sizes started while de...
Read more

New approach to screw threads in OpenSCAD

Image
This is an intellectual exercise with a practical end-result. There are better approaches to this problem, but the approach I describe here is interesting. A screw thread from a stack of discs Imagine a stack of 50 coins, stacked so that each coin is slightly offset from the one below it, with the offset moving around in a circle with each new coin. Here is what it looks like for fifty coins 20 mm in diameter and 0.5 mm thick, offset by 2 mm from a center of rotation, and stacked with a rotation offset of 30 degrees per coin ( click to enlarge any image in this article ): Obviously, this is a spiral stack of coins. But it also approximates screw threads. The thread profile looks like a sinewave rather than the trapezoidal profile of machine screw threads. Indeed, others have observed this, and used the freeware parametric CAD program OpenSCAD to make screw threads by extruding an offset circle while twisting it, as in this model on Thingiverse , for example. From a distan...
Read more