Geometric L-systems

256px-T-Square_fractal_%288_iterations%29.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.

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.

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

0 thoughts on “Geometric L-systems

  1. Brian Thompson

    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?

    Reply
  2. Mark C. Chu-Carroll

    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.

    Reply
  3. Coin

    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*?

    Reply
  4. Doug

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

    Reply

Leave a Reply