11 ms·

Not long ago, I went down the rabbit hole of space-filling curves, and learned about an obscure paper by Rolf Niedermeier, Klaus Reinhardt, and Peter Sanders th

Not long ago, I went down the rabbit hole of space-filling curves, and learned about an obscure paper by Rolf Niedermeier, Klaus Reinhardt, and Peter Sanders that introduced a rather peculiar curve with an unfortunate name: H-curve [1]. The paper mentions that H-curve preserves better locality properties compared to Hilbert curve. It fills the space with H-like shapes, hence the name. Also, like the Moore curve, it generates a loop. Space-filling curves are ridiculously easy to implement with L-system rules, and I spent a few days developing a set of axioms to express it in a rewrite system. This was a fun puzzle [2]. A => BF-F-BFFFC-F-FC+F+BF-F-BFFFC-F-FC B => BFFFC-F-FC+F+B C => C+F+BF-F-BFFFC [1] https://www.sciencedirect.com/science/article/pii/S0166218X00003267 https://www.sciencedirect.com/science/article/pii/S0166218X0... [2] https://kruzenshtern.org/25-h-curve.html https://kruzenshtern.org/25-h-curve.html

jethkl 3y ago
Cool! Obligatory https://xkcd.com/195/ https://xkcd.com/195/ Its locality properties provide a practical alternative to the Hilbert curve for this type of map. Also interesting that it is loopy.
thechao 3y ago
This is the space-filling curve we used for the last-level (4x4/16x16) tiles in the very early Larrabee work. It's a great curve!
- oneearedrabbit 3y ago
  That sounds super interesting. I would like to learn more if you're willing to share.
kragen 3y ago
hmm, i tried those rules in xfractint with 90-degree angles, and it doesn't seem to be a space-filling curve; http://canonical.org/~kragen/nothcurve.png http://canonical.org/~kragen/nothcurve.png is what i get at order 3 maybe my translation is buggy? hcurve { Angle 4 Axiom A A=BF-F-BFFFD-F-FD+F+BF-F-BFFFD-F-FD B=BFFFD-F-FD+F+B D=D+F+BF-F-BFFFD ; C is reserved in Fractint }
- oneearedrabbit 3y ago
  Fascinating. These rules are identical, but I don't have xfractint locally to reproduce/troubleshoot the issue. I think I was using https://dmitrykandalov.com/lsystem/ https://dmitrykandalov.com/lsystem/ as a playground, and it appears to be fine there. Can you try generating 1/8 or 1/4 curves to check the partial generation? Or these rules--should produce the triangular shape: A=AFFFB-F-FB+F+A B=B+F+AF-F-AFFFB
  - kragen 3y ago
    i can confirm that this works on Kandalov's site, using axiom A and angle 90: A => BF-F-BFFFD-F-FD+F+BF-F-BFFFD-F-FD B => BFFFD-F-FD+F+B D => D+F+BF-F-BFFFD maybe i'm hitting a fractint bug or unexpected behavior this recipe does work in fractint to produce the triangular shape: debug { Angle 4 Axiom A A=AFFFB-F-FB+F+A B=B+F+AF-F-AFFFB } and based on that, this produces the whole cycle: simplified { Angle 4 Axiom AF-F-AF-F- A=AFFFB-F-FB+F+A B=B+F+AF-F-AFFFB } and accordingly this works on Kandalov's site with the same axiom: A => AFFFB-F-FB+F+A B => B+F+AF-F-AFFFB oh, now i know what the problem is, D is a drawing command in fractint; i had too much D, the opposite of the usual problem. so this works: hcurve { ; by oneearedrabbit.net. See ; <https://news.ycombinator.com/item?id=38029945>. Based on "an obscure ; paper by Rolf Niedermeier, Klaus Reinhardt, and Peter Sanders that ; introduced a rather peculiar curve with an unfortunate name: H-curve ; [1]. The paper mentions that H-curve preserves better locality ; properties compared to Hilbert curve. It fills the space with H-like ; shapes, hence the name. Also, like the Moore curve, it generates a ; loop." ; <https://www.sciencedirect.com/science/article/pii/S0166218X00003267> Angle 4 Axiom A A=BF-F-BFFFX-F-FX+F+BF-F-BFFFX-F-FX B=BFFFX-F-FX+F+B X=X+F+BF-F-BFFFX ; C and D are reserved in Fractint } but i like `simplified` above better incidentally the paper seems to call it 'h-indexing'
    - kragen 3y ago
      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 in http://canonical.org/~kragen/sw/dev3/hcurvestream.py http://canonical.org/~kragen/sw/dev3/hcurvestream.py which 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): afffb-f-fb+f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afff b-f-fb+f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f- fb+f+a+f+b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f- afffbf-f-b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f- afffbfffafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb +f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a +f+b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf -f-b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf ffafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+aff fb+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfff afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a-f-f afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b +f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffb-f-fb +f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfffaf ffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a-f-faf ffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b+f +af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffb+f+afff b-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b+f+a f-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf-f-b+f+a f-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfffafffb-
andreareina 3y ago
Thought for a minute you were talking about h trees[1], but of course those aren't curves. [1]https://en.m.wikipedia.org/wiki/H_tree https://en.m.wikipedia.org/wiki/H_tree

jethkl 3y ago

Cool! Obligatory https://xkcd.com/195/ https://xkcd.com/195/ Its locality properties provide a practical alternative to the Hilbert curve for this type of map. Also interesting that it is loopy.

thechao 3y ago

This is the space-filling curve we used for the last-level (4x4/16x16) tiles in the very early Larrabee work. It's a great curve!

oneearedrabbit 3y ago
That sounds super interesting. I would like to learn more if you're willing to share.

kragen 3y ago

hmm, i tried those rules in xfractint with 90-degree angles, and it doesn't seem to be a space-filling curve; http://canonical.org/~kragen/nothcurve.png http://canonical.org/~kragen/nothcurve.png is what i get at order 3 maybe my translation is buggy? hcurve { Angle 4 Axiom A A=BF-F-BFFFD-F-FD+F+BF-F-BFFFD-F-FD B=BFFFD-F-FD+F+B D=D+F+BF-F-BFFFD ; C is reserved in Fractint }

oneearedrabbit 3y ago
Fascinating. These rules are identical, but I don't have xfractint locally to reproduce/troubleshoot the issue. I think I was using https://dmitrykandalov.com/lsystem/ https://dmitrykandalov.com/lsystem/ as a playground, and it appears to be fine there. Can you try generating 1/8 or 1/4 curves to check the partial generation? Or these rules--should produce the triangular shape: A=AFFFB-F-FB+F+A B=B+F+AF-F-AFFFB
- kragen 3y ago
  i can confirm that this works on Kandalov's site, using axiom A and angle 90: A => BF-F-BFFFD-F-FD+F+BF-F-BFFFD-F-FD B => BFFFD-F-FD+F+B D => D+F+BF-F-BFFFD maybe i'm hitting a fractint bug or unexpected behavior this recipe does work in fractint to produce the triangular shape: debug { Angle 4 Axiom A A=AFFFB-F-FB+F+A B=B+F+AF-F-AFFFB } and based on that, this produces the whole cycle: simplified { Angle 4 Axiom AF-F-AF-F- A=AFFFB-F-FB+F+A B=B+F+AF-F-AFFFB } and accordingly this works on Kandalov's site with the same axiom: A => AFFFB-F-FB+F+A B => B+F+AF-F-AFFFB oh, now i know what the problem is, D is a drawing command in fractint; i had too much D, the opposite of the usual problem. so this works: hcurve { ; by oneearedrabbit.net. See ; <https://news.ycombinator.com/item?id=38029945>. Based on "an obscure ; paper by Rolf Niedermeier, Klaus Reinhardt, and Peter Sanders that ; introduced a rather peculiar curve with an unfortunate name: H-curve ; [1]. The paper mentions that H-curve preserves better locality ; properties compared to Hilbert curve. It fills the space with H-like ; shapes, hence the name. Also, like the Moore curve, it generates a ; loop." ; <https://www.sciencedirect.com/science/article/pii/S0166218X00003267> Angle 4 Axiom A A=BF-F-BFFFX-F-FX+F+BF-F-BFFFX-F-FX B=BFFFX-F-FX+F+B X=X+F+BF-F-BFFFX ; C and D are reserved in Fractint } but i like `simplified` above better incidentally the paper seems to call it 'h-indexing'
  - kragen 3y ago
    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 in http://canonical.org/~kragen/sw/dev3/hcurvestream.py http://canonical.org/~kragen/sw/dev3/hcurvestream.py which 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): afffb-f-fb+f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afff b-f-fb+f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f- fb+f+a+f+b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f- afffbf-f-b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f- afffbfffafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb +f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a +f+b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf -f-b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf ffafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+aff fb+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfff afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a-f-f afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b +f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffb-f-fb +f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfffaf ffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a-f-faf ffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b+f +af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffb+f+afff b-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b+f+a f-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf-f-b+f+a f-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfffafffb-

andreareina 3y ago

Thought for a minute you were talking about h trees[1], but of course those aren't curves. [1]https://en.m.wikipedia.org/wiki/H_tree https://en.m.wikipedia.org/wiki/H_tree