Mark
Dow
Geek art
Simple recursive systems and fractal patterns
Thue-Morse sequence tilings
Visually interesting two dimensional tilings can be constructed by
abstracting the one dimensional Thue-Morse sequence to two dimensions
and choosing compatible motifs. The Thue-Morse sequence's locally
symmetric, highly repetative and redundant, but non-periodic
properties result in tilings with the visual impression of order
within disorder.
Neigborhood dependent Thue-Morse tilings
Ted Bell motivated me to write a program for
constructing these tilings after I showed him a short description of
the
Thue-Morse sequence
from a book (chapter 30 of M.R. Schroeder "Number Theory in Science and
Communication", Springer, Third edition 1997). He realized and sketched
the basic tiling
scheme, a natural dual division of the plane based on the tiling, and a
higher order pattern that emerged. He also devised and made a sketch of
this Gray code
Thue-Morse binary fractal pattern.
Since then we have thought about how to find interesting motifs (motifs
such that edges match in non-trivial ways), variations of the basic
tiling pattern, and extensions to sequences with more than two symbols.
The Thue-Morse sequence
The Thue-Morse sequence
is a non-periodic sequence of any two symbols:
a b b a b a a b b a a b a b b a b a a b a b b a a b b a b a a b ...
or
There are several methods for constructing the sequence. One algorithm involves repeated concatenation;
{
Start with one symbol (a, or a black square) and concate its
complementary symbol string (b, or a white square).
Repeat this complementary concatenation using the result as the input to the next repetion.
}
Another method is more general - a recursive symbol replacement system.
Starting with a, replace a with a b and b with b a, and then repeat
these replacement rules indefinitely, always using the results as the input for the next generation:
a; { a -> a b }, { b -> b a }
or
Both algorithms result in the same series of generations of symbol strings:
generation 0:
a
generation 1:
a b
generation 2:
a b b a
generation 3:
a b b a b a a b
generation 4:
a b b a b a a b b a a b a b b a
generation 5:
a b b a b a a b b a a b a b b a b a a b a b b a a b b a b a a b
.
.
.
or
All sub-sequences (sets of
adjacent symbols) will reoccur in this sequence. This can be
demonstrated using the concatenation algorithm; since the complement of
every sub-sequence is repeated, after two repetitions the original
sub-sequence (the complement of the complement) will occur.
But any sub-sequence never reoccurs at the same spacing throughout the
sequence. So the sequence is non-periodic, but filled with redundant
sub-sequences.
Also, some substrings never
reoccur adjacent to each other. For example a a a a and a b b a a b b a doesn't occur anywhere in the sequence. In fact, three of the same symbols, or three sets of
any sub-sequence, in a row (e.g. a a a and b b b, or b b a a b b) doesn't occur. This
property is called "cube-free".
[To Do: Overlap free, WWa also doesn't occur, see Mathworld and Wikipedia]
Construction of a 2-D Thue-Morse pattern
A 2-D Thue-Morse pattern, where each row and column is a Thue-Morse
sequence, can also be formed by a recursive concatenation as described
above. The complement of an array of symbols is concatenated to itself,
first in one direction and then the other:
1st generation
(corresponding to :
a b ...
b a
... )
The two symbols, distinguished by color (black and white). |
2nd generation (corresponding to :
a b b a ...
b a a b
b a a b
a b b a
... )
Note that rows and columns are all Thue-Morse sequences. |
3rd generation
Odd generations are not bilaterally symmetric (horizontally or vertically), but are symmetric across the diagonals. |
4th generation
Even generations are bilaterally symmetric as well as symmetric across the diagonals. |
8th order, click for large version |
A recursive symbol replacement system that results in the same 2-D Thue-Morse pattern:
|
 |
... |
For examples and discussion of similar symbol replacement systems, see "Simple recursive systems and simple fractal patterns".
[To Do: L-shaped patterns don't occur in 2-D, and other properties.]
All of the tilings on this page are formed by replacing these 2-D
arrays of symbols with square or rectangular motifs; the motifs
are used as symbols. Many of the tilings are dual: the motifs of the
two tiles
are geometrically related. The two
motifs can be related by a rotation, mirroring, luminance inversion, or any different coloring of the same pattern.
Redundant Quadrapii
A basis motif, or tile, formed of logarithmic spirals with a pitch of pi/4. See Logarithmic spirals, waves and tilings for details and Matlab code for generating logarithmic spiral divisions of the plane. |
Two square motifs, side-by-side, formed by a combination of 2x4 basis motifs rotated and
mirrored. Note that the right set of 2x2 basis motifs are a 90 degree
rotation of the left set of 2x2 basis motifs.
The recursive replacement system that results in the 2-D Thue-Morse pattern.
|
Fourth order Thue-Morse tiling of the motif pair. |
The tiling, colored by shapes of contiguous regions. Shape relief rendering done with Matlab
morphological erosion and Space Software.
[To Do: Add example volume and Matlab erosion code.]
|
Orthologia
An imaginary beast, a bugit, based on a logarithmic
spiral similarity tiling and colored by the Thue-Morse sequence. [To Do: Context
of a square tesselation and Thue-Morse coloring.]
The basis pattern (at left) is an infinite division of the plane by logarithmic spirals, a binary fractal. It's a checkerboard division (8x2) of the
plane by logarithmic spirals with a pitch of +/- pi/4 radians. The
checkerboard is colored (orthogonal to the contours) by repetition of the third generation
(23 = 8 element) Thue-Morse sequence
[0 1 1 0 1 0 0 1], where 1 and 0 represent black and white. The relative phase between the two sets of opposite
chirality spirals rotates through pi/2 radians; in this example the
phase of one set is fixed.
There is a nice bi-stable perception illusion in the animation (above left): when I
first see it, I percieve a wholistic pattern rotating CW and shrinking.
But after a short time, I see half the contours as fixed, and the other
half rotating (with no shrinking). Try fixating on a single edge point to experience the second percept.
Also see description, notes and code for the Orthologia images, and Logarithmic spirals, waves and tilings for details and Matlab code for generating logarithmic spiral divisions of the plane.
Four knot
A 2-D Thue-Morse pattern where the symbols are
replaced by a motif that visually connects all adjacent symbols. The
result is a woven pattern, with each "strand" forming a simple closed
loop.
The two square motifs, side-by-side, where each motif is a pi/2 rotation of the other.
The recursive replacement system that results in the 2-D Thue-Morse pattern.
|
Oblique viewpoint rendering of the 3-D motif used to construct Thue-Morse chain images. (Stereo pair, cross-view.)
Constructed and rendered with Space Software, using a single chiral spline segment, rotated/mirrored four times. (Credit to Greg Scott for writing the spline code.)
curveA_b_4.vol.gz (2 MB) |
The Thue-Morse tiling. |
The pattern after a pi/4 rotation and coloring of connected
elements -- only those elements that are closed on this portion of the
potentially infinite tiling.
|
Matlab command (for the Thue-Morse tiling of this motif pair):
y
Why this works (nested circuits in this weave
pattern, colored by connectivity in the left image) is a mystery
to me. How would a larger Thue-Morse pattern with the same motifs be
connected? I designed the motif, shading and coloring, but I didn't
design the pattern; I found it.
Thue-Morse tilings of other motifs
3-D Thue-Morse pattern (Thue-Morse cube)
A 3-D (or higher dimensional) Thue-Morse pattern is formed by extension
of the one and two dimensional algorithms (see above). The recursive
symbol replacement system is represented as:
where the symbols (black, white squares) occupy a cube's coordinate volume elements.
|
 |
| A surface rendering (sterero pair, cross view) of the 3-D Thue-Morse
pattern, or Thue-Morse cube, using empty and filled space as symbols.
Third generation, 8x8x8. |
A 2-D slice through a
symmetry plane of the 3-D Thue-Morse cube (at left). Seventh
generation, 128x128x128. The long range self-similar structure of the
Thue-Morse pattern is more
easily seen in this slice than in the 2-D square system's pattern.
Notice the slightly lighter/darker trapezoids that repeat at different
scales; it is a discrete similarity tiling. |
[To Do: Reference and link to 3-D L-system code. Include example volumes.]
Matlab code for general Thue-Morse tilings
A Matlab program used for most Thue-Morse tilings,
those that directly replace each symbol with one of two motifs:
Many of these tilings are formed by replacing each
symbol of a Thue-Morse pattern with a square (or rectangular)
image. This can be done manually using copy/paste in an image editor,
but for large tilings it is convenient to automate the process. The one dimensional Thue-Morse sequence can be easily generated
using Matlab's syntax. Using [0,1] as the symbols, a sequence that is
2n elements long is generated (using the logical NOT operator "~") with the
code:
{
% Construct a Thue-Morse vector of length 2^n:
vctTM = 0; % initial element [0,1]
for i = 1 : n % where n is the number of generations
% Double the length, using the compliment of the original array element(s) as the new element(s).
vctTM( length( vctTM ) + 1 : 2*length( vctTM ) ) = ~vctTM;
end
}
This can be extended to the two dimensional
Thue-Morse pattern, where each row and column is a Thue-Morse sequence.
I have generalized this patten generation, extending
it to patterns and tilings of any one or two dimensional L-system on a square grid, not only the Thue-Morse system. See L-system program and code, and the work-in-progress "Simple recurrent sequences and simple fractal patterns"
for related examples. The syntax for generating the 2-D Thue-Morse pattern is:
>> imageMatrix = L_system_tiling( 'TM', [ng], 2, 1, 0, 'motif.jpg', 0, [0 1; 1 0], [1 0; 0 1] );
where ng is the number of generations desired, and motif.jpg is an image file containing a pair of side-by-side motifs.
Matlab code for neigborhood dependent Thue-Morse tilings
Some of these tilings are neighborhood
dependent: the square (or rectangular) image that replaces the symbol
depends on what symbols surround the symbol that is replaced. For the
Thue-Morse pattern there are a only a small set of possible nearest
neighbor patterns. [To Do: Illustrate the six nearest neighbor
configuations and rotations.]
A Matlab program used for a few special cases:
The program is not general as it only handles a
couple kinds of neighborhood relationships and possible replacement .
How it operates and the reasoning behind the particular orderings is
not obvious, even to me.
Example usage (see file header for details):
>> imageMatrix = Thue_Morse_tiling( [ng],'motif.jpg' , 2 );
where ng is the number of generations desired, and motif.jpg is an image file containing a motif specified by a 2x4 set of basis elements.
The code is reasonably clean, but a bit hard to follow, not very flexible or well documented.
[ To Do: Ideas for the future, references ]
------------------------------------
There are no restrictions on use of the images or code
on this page. Claiming to be the originator of the material,
explicitly or implicitly, is bad karma. A link (if appropriate), a note to dow[at]uoregon.edu, and credit are appreciated but not required.
Comments are welcome (dow[at]uoregon.edu).
Oblique viewpoint rendering of the 3-D motif used to construct Thue-Morse chain images. (Stereo pair, cross-view.)
