[oneearedrabbit]

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/S0166218X0...

[2] https://kruzenshtern.org/25-h-curve.html

[thechao]

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]

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

[kragen]

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 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]

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/ 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]

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]

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

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-

[kragen]

i realize i never posted working image links

http://canonical.org/~kragen/hcurve.png

http://canonical.org/~kragen/hcurvetri.png

[andreareina]

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

[jethkl]

Cool! Obligatory 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.