Hilbert space filling curve for (non-square) arbitrary proportions

Question

Is there any extension to the Hilbert space/plane filling curve that maps a non-square surface to a vector/line [for image mapping to vector]?

Eduardo

Yes, but requiring over or under-sampling to adapt to the new dimensions. But under sampling is what I wanted to avoid using this kind of curve. – Eduardo

Answer 1

I just looked for this myself today. I found this page by Lutz Tautenhahn:

"Draw A Space-Filling Curve of Arbitrary Size"

The algorithm doesn't have a name, he doesn't reference anyone else and the sketch suggests he came up with it himself. So until someone with more knowledge about the topic comes along let's call it a Tautenhahn Curve? For powers of 2 it turns back into a Hilbert curve though!

Still digging through the messy source code, no idea what the Big-O overhead and so forth will end up as.

It looks like he partitions space as "evenly" as possible from the top down, so assuming the overhead isn't too great it's probably a good candidate for what you want to do.

EDIT: Although I doubt that you'll see this so many years later, I recently came across a paper from 2000 with another approach that may actually be useful in your specific case:

"Context-based Space Filling Curves" by Revital Dafner, Daniel Cohen-Or and Yossi Matias

It is a method to construct a space-filling curve that is "optimal" in regards to the changes in underlying image data.

Janinajanine

While this may answer the question, it is better to provide the actual information here and not just a link. Link-only answers are not considered good answers and will probably be deleted. – Mistrustful

I understand that, but the problem is that I haven't quite figured out how it works myself yet. The source code for the demo is horribly written, and the explanation is a scan of a sketched proof on paper. I'm working on it but figured that others might be faster at figuring this out than I am, so I shared the link in the sense of "the answer is in here somewhere, maybe you can beat me do decrypting this." – Janinajanine

@Job:I tried 40x45 and it also works. Amazing finds! Did you decrypt it? – Liter

This algorithm certainly produces beautiful curves that are about what I'm looking for -- I, too, anxiously await someone figuring out its poorly-documented magic sauce... – Rider

@Janinajanine I'm still reading the sketches, but I guess that the "Big-O overhead" you mentioned is actually O* > 1!, where ! being the exclamation mark rather than factorial. The O* is used to denote a different odd number than O. But he drew 2 identical cases of O-O*. I guess maybe 1 of these should be transposed? – Cuttler

Some further updates: I've ported a Python version. The most complicated function go() was translated by using vim editing commands as much as possible. I noticed that some cases don't match the js outputs, e.g. when either side is >= 3/2 of the other (e.g. x=10, y=30). I couldn't figure out what's is causing the inconsistency. If anyone spots anything pls let me know. – Cuttler

Answer 2

I have written an algorithm that generates a Hilbert-like curve for rectangles of arbitrary size in 2D and 3D. Example for 55x31: curve55x31

The idea is to recursively apply a Hilbert-like template but avoid odd sizes when halving the domain dimensions. If the dimensions happen to be powers of two, the classic Hilbert curve is generated.

def gilbert2d(x, y, ax, ay, bx, by):
    """
    Generalized Hilbert ('gilbert') space-filling curve for arbitrary-sized
    2D rectangular grids.
    """

    w = abs(ax + ay)
    h = abs(bx + by)

    (dax, day) = (sgn(ax), sgn(ay)) # unit major direction
    (dbx, dby) = (sgn(bx), sgn(by)) # unit orthogonal direction

    if h == 1:
        # trivial row fill
        for i in range(0, w):
            print x, y
            (x, y) = (x + dax, y + day)
        return

    if w == 1:
        # trivial column fill
        for i in range(0, h):
            print x, y
            (x, y) = (x + dbx, y + dby)
        return

    (ax2, ay2) = (ax/2, ay/2)
    (bx2, by2) = (bx/2, by/2)

    w2 = abs(ax2 + ay2)
    h2 = abs(bx2 + by2)

    if 2*w > 3*h:
        if (w2 % 2) and (w > 2):
            # prefer even steps
            (ax2, ay2) = (ax2 + dax, ay2 + day)

        # long case: split in two parts only
        gilbert2d(x, y, ax2, ay2, bx, by)
        gilbert2d(x+ax2, y+ay2, ax-ax2, ay-ay2, bx, by)

    else:
        if (h2 % 2) and (h > 2):
            # prefer even steps
            (bx2, by2) = (bx2 + dbx, by2 + dby)

        # standard case: one step up, one long horizontal, one step down
        gilbert2d(x, y, bx2, by2, ax2, ay2)
        gilbert2d(x+bx2, y+by2, ax, ay, bx-bx2, by-by2)
        gilbert2d(x+(ax-dax)+(bx2-dbx), y+(ay-day)+(by2-dby),
                 -bx2, -by2, -(ax-ax2), -(ay-ay2))

def main():
    width = int(sys.argv[1])
    height = int(sys.argv[2])

    if width >= height:
        gilbert2d(0, 0, width, 0, 0, height)
    else:
        gilbert2d(0, 0, 0, height, width, 0)

A 3D version and more documentation is available at https://github.com/jakubcerveny/gilbert

Omnipotence

Answer 3

Since this answer is significantly different from my previous one I'll post it separately: in the last two years I wrote two "space-filling curves of arbitrary size" algorithms. They have a couple of caveats:

• they are allowed to take diagonal steps.
• one of them is a Hamiltonian curve, meaning it forms a closed loop

Whether or not either of these things matters depends on your use-case I guess. Anyway, here are the notebooks explaining how they work in exhausting detail, with implementations in JavaScript:

https://observablehq.com/@jobleonard/arbitrary-hamiltonian-curves

https://observablehq.com/@jobleonard/peanoish-curves-of-arbitrary-size

Janinajanine

Answer 4

There are adaptive hilbert curves but imo it is very difficult and for other use but you can map a "normal" hilbert curve to any rectangles, too.

Liter

How is it done? I couldn't find any non-square example nor tutorial. – Eduardo

You can treat the co ordinate as binary and interleave it. Then treat it as base-4 number. This is a z order curve. Works similar with hilbert curves! – Liter

Read this question and answer:#27345465 – Liter