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

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

The water rocket: Thrust from water

Image
Launch tube thrust Thrust from air Once the rocket has left the launch tube, the water thrust phase of the flight begins. But before we begin those calculations, we need to have equations for ballistic flight, which is the last step described in the introduction . Why? Because during ballistic flight (coasting through the air), the only forces acting on the rocket are gravity and wind drag — but these are acting on the rocket during the thrust phase too. Ballistic flight is exactly the same, just without the thrust. Ballistic flight We need to know how gravity and drag affect acceleration, velocity, and ultimately altitude during all thrust phases as well as the ballistic trajectory afterward, so we'll start with the ballistic flight equations. Air resistance First we need to get the ambient air density. Denser air results in higher drag, and dry air is more dense than moist air. To get the density, we first need to know the partial pressure of water vapor in the air. T
Read more