Re:Hilbert curve: The famous space filling curve drawn with ...
by kragen on Friday October 27, 2023 @10:43PM
(#38046595)
incidentally, this slight variant l-system, which is probably what you meant
a where
a -> afffb-f-fb+f+a
b -> b+f+af-f-afffb
has the property that the axiom is a proper prefix of the axiom's expansion,
which turns out to be equivalent to the property
that every generation is a proper prefix of the following generation;
this means that in a sense each one is "approaching a limit"
of a single infinite string,
in the sense that it's a successively longer prefix of that string.
this infinite string,
called a 'morphic word',
is a fixed point of the mapping
the l-system does each generation
this is literally a numerical approximation if you treat the string
as a fractional number in some base, e.g., base 10 with a=1, b=2, f=3, +=4, -=5
with that interpretation, the first approximation 'a' is 0.1, the second approximation 'afffb-f-fb+f+a' is 0.13332535324341, the third approximation 'afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a' is 0.133325353243413332434135351333253532434135351333243413332535324341, and so on.
the thue-morse sequence can be generated in the same way with the l-system
0 where 0 -> 01 and 1 -> 10
although the so-called fibonacci word is slightly simpler
a where a -> ab and b -> a
all of the above morphic words are aperiodic, though it's trivial to design a periodic morphic word
a program to output the infinite morphic word of movement commands for the h-curve of a single triangle is
queue = ['a'], []
d = dict(a='afffb-f-fb+f+a', b='b+f+af-f-afffb')
while True:
for item in queue[0]:
for c in item:
n = d.get(c, c)
yield n
queue[1].append(n)
queue = queue[1][::-1], queue[0] # amortized constant time
queue[1].clear()
this is literally a numerical approximation if you treat the string as a fractional number in some base, e.g., base 10 with a=1, b=2, f=3, +=4, -=5
with that interpretation, the first approximation 'a' is 0.1, the second approximation 'afffb-f-fb+f+a' is 0.13332535324341, the third approximation 'afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a' is 0.133325353243413332434135351333253532434135351333243413332535324341, and so on.
the thue-morse sequence can be generated in the same way with the l-system
although the so-called fibonacci word is slightly simpler all of the above morphic words are aperiodic, though it's trivial to design a periodic morphic worda program to output the infinite morphic word of movement commands for the h-curve of a single triangle is
this is in http://canonical.org/~kragen/sw/dev3/hcurvestream.pywhich outputs about 5MB/s on this palmtop but will slow down as it runs into swap after generating less than the size of RAM in output
the output begins (via fold -w 70):