[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

[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.