Hilbert curve: The space filling curve drawn with JavaScript | Hacker News Reader

Hilbert curve: The space filling curve drawn with JavaScript

jsxgraph.uni-bayreuth.de

96 pointssusam33 comments

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

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.

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!

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

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
    }

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

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'

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-

i realize i never posted working image links

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

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

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

Some time ago I made an animation of a Hilbert curve with sections transitioning between levels. As simple as it is, it's kind of fun to watch.

https://ehq.com/rloop2.svg

I made a little hilbert curve demo for an interview take home test a while ago!

https://graypegg.com/hilbert

(https://github.com/graypegg/hilbertcurveplayground)

Maps weather data, sorted by date onto the curve. Makes the seasons obvious since they get grouped together!

In 1990, I included the Hilbert Curve in my senior thesis for my BS in Math, which I presented to all the professors in our math department. Years later, one of those professors became a family friend. He was an incredibly supportive mentor to multiple people in our family. After he passed away last year, I learned that his great-great grandfather was David Hilbert, creator of this curve. It must have been fun to see some of his family's work displayed in one of his student's theses.

https://www.hmc.edu/in-memoriam/hank-krieger/

You realize it was his mathematical great-great grandfather, right?

That means, his PhD advisor's advisor's advisor's advisor. There are a few thousand mathematicians who can claim that: https://www.mathgenealogy.org/id.php?id=7298

Silly me, I thought mathematicians reproduced by budding. I assumed that's what they did while reclusing in their mountain shacks between public appearances.

I worked at that chair at Uni Bayreuth for a while. Here is the github repo (webpage is hugged to death) https://github.com/jsxgraph/jsxgraph

Shoutout to Prof. Wassermann for keeping up the good work.

I love putting hilbert curves into various simulation and building games - you often get interesting results! And if you don't, it at least looks cool.

One time I wrote some ruby and some lua to generate a hilbert curve in Factorio - I'm pretty happy with the result: https://github.com/kkuchta/factorio_hilbert

It's nice to see just how popular Hilbert curves are. For me it touches the same nerve that Conway's Game of Life does.

I threw together a hacky demo of the Hilbert curve and some other l-system curve for a middle school computer club I ran way back when. Not the best UI in the world, but it shows you either the string substitutions following each l-system ruleset, or with "show canvas" checked each click draws the next generation.

https://autery.net/pages/l-systems.html

One beautiful quality of these curves is that they can nicely reduce a two (or n) dimensional space down to one, so that neighbors can be found simply by looking at ranges.

https://stackoverflow.com/questions/499166/mapping-n-dimensi...

coincidentally i wrote code to render a hilbert curve in emoji the other day. it was three or four lines of golfed python

    #!/usr/bin/python3
    T=['a'];[T.append(''.join(dict(a='lbffraffarffbl',b='rafflbffblffar').get(c,c)for c in T[-1]))for i in 'abcd'];D,V=[0],1
    for c in T[-1]:M,T=dict(f=(1,1),r=(0,1j),l=(0,-1j)).get(c,(0,1));D.append(D[-1]+M*V);V*=T
    X=range(31);print('\n'.join(''.join('⬜'[j-i*1j in D]for j in X)for i in X))

hn silently censors that in a way that breaks the code but the original is at http://canonical.org/~kragen/sw/dev3/hilbert.py

there is an almost perfectly correct explanation of the code by gpt-4 at https://bin.gy/altypsisca

the only problem was that gpt-4 guessed wrong about which particular fractal was being drawn

i think the turtle-graphics formulation of the hilbert curve that underlies this l-system is nicer than the manhattan formulation in the linked js. i'm undecided about whether the l-system formulation as string rewrite rules is better or worse than the explicit recursion with conditionals used in the js. fractint's l-system engine includes a `!` operator which swaps left and right, which i think could make the hilbert curve simpler, though the definition in fractint.l doesn't

sudo apt install xfractint and type tlsystem and hit enter to explore more l-systems`

arguably a formulation in terms of a shape grammar or iterated function system would be a better fit

also, if l-systems are the kind of thing you like, you'll probably enjoy http://canonical.org/~kragen/sw/dev3/skitch

I once made a visualisation of the Hilbert curve evaluated at 2048 random points: https://mathstodon.xyz/@OscarCunningham/108889112101425236

Your post sent me down a rabbit hole, thanks!

Google’s S2, geometry on the sphere, cells and Hilbert curve

https://news.ycombinator.com/item?id=10066616

I've always thought S2 was a clever name for something built with the Hilbert curve. (Look at the shape of the glyphs.)

There's a simple way to draw the curve at full precision using SVG:

   <rect x="0" y="0" width="1" height="1" />

I first heard about this the other day when Clough42 (on Youtube) was talking about using the Hilbert curve setting for the bottom layer of a 3d print to make that layer look better for his final product. I haven't tried it on my own prints, but mine typically don't show the lines on the first layer, so I'm not sure it would make a difference in my prints. But maybe I'm over-extruding a bit there.

It took me a while to see the slide just below the graphic. I was expecting to click or press space to get the next level.

There is some infesting/weird aliasing at the 8 and 9 level (at least in my screen). I'm almost sure it's aliasing, not a real density difference.

I'm not so sure. Some of what looks like an artifact on level 8 is already more clearly visible on level 7 as a density difference. Do we talk about the same thing, some white lines which are not often crossed?

The definition of the Hilbert curve is a line of width 0, so my question makes no theoretical sense.

Anyway, a real example has a line of non zero width, let's asume 1/2^n. Centered? How even is the average dendity distribution? Are the crosses real or an artifact of the pixels in my screen? I don't know and I'm curious?

This curve always reminds me of isometric embeddings:

https://medium.com/coffee-shop-math/coffee-shop-math-isometr...

I also have one of those: https://jonathan-potter.github.io/hilbert-curve/

A fun aspect of this space filling curve is that it can be used for the infill pattern of a 3D print.

Can, but I can't imagine there's a metric that's outperformed by the Hilbert curve, compared to the usual infill patterns.

I never really got the point of doing that as opposed to just a regular linear 100% fill which is a lot less stress on the motors and belts.

Reply on news.ycombinator.com