Home › Mark's Projects › Simple recursive systems and fractal patterns

Simplest 2-D block replacement L-systems

Wed, 2007-06-13 12:04 — Mark Dow

This diagram shows all 2-D square recurrent patterns after 5 iterations. The starting symbol is black; starting with white would result in complementary coloring. The rules are displayed at the top/left of the row/column of the resulting pattern.

 

The 2-D Thue-Morse patterns appear near the diagonal, to the lower right of center. [To Do: Oversample this diagram x2, change title.] Right click to view full scale:

Here's the corresponding seventh order image that shows longer range structure (right click to view full scale):


 

[To Do: Separate topic -- distinguish periodic, non-periodic, aperiodic systems.]

Penrose tilings are also 2-D L-Systems. But whereas Penrose tilings are aperiodic (they can tile the plane but not in a periodic way) these are non-periodic (they can tile the plane in a periodic way but are not arranged in a periodic pattern). In Penrose tilings, the tile shapes uniquely restrict the possibilities for an infinite tiling, but here the square shape of the tile does not constrain the algorithm that generates them.

 

Complementary corners

Complementary corners motif
The motif, double-diagonal_3.png

Complementary corners, algorithm graphic

 Complementary corners pattern, by generation

Matlab command:
>> imOut = L_System_tiling( 'CC',  [ng], 2, 1, 0, 'double-diagonal_3.png', 0, [0 0; 0 1], [0 1; 1 1] );
where [ng] is the number of generations.

 

5th generation pattern
5th generation pattern

 

Complementary corners, link to
link to full version, with contiguous regions colored orange or black

LSystem_array_2_7.png
‹ Notes: Three symbol Thue-Morse and Period-tripling sequence rulesup2x2 4 rotation cyclic ›

Comments

Fri, 2007-06-15 15:50 — PSR

anonoperiodicity

because youre distinguishing these from penrose tilings by this virtue, whats the difference between aperiodic and nonperiodic? ( I thought they were essentially synonyms meaning no repetition)

Does the 3rd example develop any interesting visible higher order structure when the number of iterations are increased and the pixel sized is reduced?

 


Sat, 2007-06-16 00:24 — Mark Dow

not periodic

Yes, aperiodic and non-periodic are traditionally synonyms, but the tiling community uses the distinction for a specific purpose. Penrose tile shapes prevent them from being put together (covering the plane) in such a way that they are periodic. Another way of saying this is that only non-periodic tilings are possible. With square tiles, periodic tilings are possible, and it is just this arrangement of B/W tiles that are non-periodic.

I added a graphic with all 2 symbol systems.

Yes the third example (and the other two) do show longer range structure, but it is subtle because no big clumps (larger than 2 of the same color) ever occurs. But it is non-periodic, so new structure occurs at all larger scales, with "diminishing novelty". Here's a big one of the third:

Tue, 2007-06-19 17:09 — PSR

figure

Your two-symbol square L-system figure is REAlly nice. Well done and clear, but I don't have a full grasp of exactly why you did this and why certain patterns arise. My confusion regarding this could probably be resolved with a brief chat over coffee but I still want to figure out a way of doing the same thing (coffee chat) online -I may turn a few of your posts into forum topics...

Anyway, I think this whole topic of TMs and minimal L-systems would make a GReat publication. What do you think Mark, about the prospect of fleshing this out a bit and maybe submitting it to one of the online visual-math journals?

 Regardless, is there anything significant about the appearance of Sierpinski fractals in the table or is it just a common occurrence based on the 3-block 'L' shaped primitives that cause them? And is there anything particularly interesting about the cognate partners to the Sierpinskis diagonally across on the other side of the table (the migratory bird shaped patterns...)?



Tue, 2007-06-19 22:00 — Mark Dow

simplest fractal meaning

Yes, I'm currently jazzed about this diagram and why it looks so nice, and why it's not obvious.

Why: Ted and I talked about and sketched out >2 symbol Thue-Morse systems, and it dawned on me that the way to program tilings was to use L-Systems (string rewritting). By the time I got around to doing it (months) it turned out to be very simple -- and the program that makes these can be used for any number of symbols, any dimension, any (rectilinear) rule set. So once I had tried a couple four symbol rules it occurred to me to write out the interesting 2-D two rule patterns. I had a guess (wrong) about which were interesting (showed non-periodicity, nested long range structure), and it occured to Ted and I simultaneously to make this grid. This inspired me to go even simpler and do the 1-D sequences. This brought up a whole other thought about how these pattens and sequences relate to integers -- I can't figure that out yet, I just know it's interesting. There should be a formalism such that all (not any) of these, and all system in any dimension, can be described by operations on basis sequences or the rules that create the sequences.

So I don't know why this grid is the way it is. Certain things are starting to make sense, but there are several mysteries. What's with the asymmetries across the diagonals, and what about minor diagonals (within sub-blocks)? Can some of these be expressed in terms of others (e.g. are some complements of others)? Only some of these are fractal (some are periodic, not technically fractal, although they are produced in the same fasion. Why this number of fractals? Why are some over-represented?

I think this set may form a basis for a group -- operations between all combinations always form a pattern that is within a finite set of patterns. That's speculation, but it will be interesting if true: what's the group and is it finite?

All in all, the chart makes sense to me as a way of describing rectilinear fractals. I've never seen it done this way and yet it seems an obvious way to show how these basic rules result in a basic set of patterns. And most surprising, it's not as simple as I'd expect.

I'd like to flesh it out, and you're welcome to help. I've got lots of tidbits about particular pieces, and several ideas about others. For example, all the previous TM stuff refers to two squares of this chart. That space filling curve I stumbled on is about four more of these squares. Some of the squares (e.g. the "doves") I don't recognize.