Geometric L-systems

i-1fc828f4b2c2eb235077bbedaf7665fa-256px-T-Square_fractal_(8_iterations).png

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.

i-abd0d72b18677f441e3c6204c539a51a-tsquare.png

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.

i-76eef61d5aa3b3261ebec9933befa297-g-lsystem-tsquare.png

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.)

Tags

More like this

In the post about Koch curves, I talked about how a grammar-rewrite system could be used to describe fractals. There's a bit more to the grammar idea that I originally suggested. There's something called an L-system (short for Lindenmayer system, after Aristid Lindenmayer, who invented it for…
I just finally got my copy of Mandelbrot's book on fractals. In his discussion of curve fractals (that is, fractals formed from an unbroken line, isomorphic to the interval (0,1)), he describes them in terms of shorelines rather than borders. I've got to admit that his metaphor is better than…
Most of the fractals that I've written about so far - including all of the L-system fractals - are examples of something called iterated function systems. Speaking informally, an iterated function system is one where you have a transformation function which you apply repeatedly. Most iterated…
One of the strangest things in fractals, at least to me, is the idea of space filling curves. A space filling curve is a curve constructed using a Koch-like replacement method, but instead of being self-avoiding, it eventually contacts itself at every point. What's so strange about these things…

It doesn't seem like it would be that difficult to come up with a traditional L-system to describe the boundary of this geometric L-system. The first square is composed of S Straights and C Corners. Replace each S with SSS and each C with C'CSCSCC' (C' is -90 degrees).

That works... right?

By Brian Thompson (not verified) on 02 Aug 2007 #permalink

it's quite obviously got a finite area inside of it; but its boundary is infinite.

Oh god, it's Gabriel's Trumpet all over again!

Brian:

You *can* come up with an L-system formalism for anything that you can do with any of the variants of geometric L-systems; that's why we call them a kind of L-system. The advantage of the geometric L-system isn't that it can do fundamentally different things than an L-system, but that it's *easier* to create and understand the L-system presented in geometric form.

Looking at the geometric L-system for the T-square, it's obvious that it's a description of the T-square. It was easy to draw, and it's easy to understand what it does. In conventional string format, you need to really think about it - you need to ask if you got the L-system rule right. It's hard to figure it out; looking at your rule, I'm confused about what the straights do. (You've got "C'C"; so obviously, your corners include some edge portions. I'm not sure why C'C doesn't need a straight, but CSC does.)

That's the point of the geometric L-system: instead of shoehorning geometry into symbols, keep it as geometry.

The advantage of the geometric L-system isn't that it can do fundamentally different things than an L-system, but that it's *easier* to create and understand the L-system presented in geometric form.

Would I be correct though in guessing that the symbolic L-system will always be easier to *compute*?

[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.]

This sounds a lot like improper integrals. What a horrible name for such a neat concept really.