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

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.

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