Geometric L-systems

As I alluded to yesterday, there's an analogue of L-systems for things more complicated than curves. In fact, there are a variety of them. I'm going to show you one simple example, called a geometric L-system, which is useful for generating a certain kind of iterated function fractal; other variants work in a similar way.

I'm going to show it to you in the context of an interesting fractal figure, called the T-square fractal. The T-square starts with a colored square centered inside of a white square twice its size. In
each iteration, for each of the outermost squares, you create a square one-half it's size, and lay a copy of that on each exposed corner of the outermost square, so that the new square overlaps with a square 1/2 its size.

That sounds confusing, but it's pretty simple when you see it visually. Here's a copy of the T-square after 4 iterations. You can see what I mean about how much easier it is to see visually. The T-square looks much more interesting after a lot of iterations - at the top of this post, there's a copy of it from wikipedia after a bunch of iterations. It's an interesting figure in its own right: it's quite obviously got a finite area inside of it; but its boundary is infinite. A lot of people actually have a hard time grasping that: the idea of a adding constantly decreasing segments to a finite boundary doesn't seem like it should be infinite. It doesn't make good intuitive sense. But it's pretty easy to show.

Let the length of the sides of the original square be X, so its boundary is 4X. Then in the first step, you add four squares,
each of which eliminate 1/2 X from the boundary of the original square, but add X/2+X/2+X/4+X/4 to it. So
after one step, the length of the boundary is 4X+4(-1/2X+3/2X) = 4X+4X: the boundary has doubled. In subsequent steps, we'll only be adding 3 squares for each of the outermost boxes - in the next step,
we'll expand the 4 outermost boxes by adding three new ones. So the boundary contributed by each outer square will be 7/4X. And the next iteration will increase the perimiter of those outermost perimeters by the same proportion. The length added to the boundary isn't decreasing with each iteration after the first: the length added by each new box is cut in reduced; but the number of boxes added more than compensates for the reduction.

But let's get back to the geometric L-system. The idea is quite simple; instead of using an L-system over symbols and strings, we're going to do something like an L-system over shapes and patterns. So the initiator is a geometric figure; the left-hand side of a rule is a pattern that matches a part of a shape, and the right hand side shows how to replace the part of the shape that matches the pattern. The pattern can be freely rotated to find a match. Here's the one rule from the geometric L-system for the T-square.

See? Simple! (Ok, not exactly simple, but it's not rocket science either. It's a quite
comprehensible way of describing how to construct some pretty hairy iterated function fractals.)