img2hilbert.py

from PIL import Image
import numpy as np
import itertools
flatten = itertools.chain.from_iterable

max_depth = 8

img = Image.open('David_Hilbert_postcard_edit2.png')
img = img.convert('L').resize((2**max_depth,) * 2)
img = img.point(lambda i: (1 - i/255 * 0.75) * 128 )

def img2hilbert(img, remainder):
    total = np.sum(img) / 128.0 + remainder
    assert img.width == img.height
    assert img.width & (img.width - 1) == 0
    if img.width <= 1 or img.height <= 1 or total <= img.width:
        path = ((img.width, img.height),)
        return (path, total - img.width)
    else:
        x = img.width
        y = img.height
        a = x // 2
        b = y // 2
        quadrants = (
            img.crop((0, 0, a, b)).transpose(Image.TRANSPOSE),
            img.crop((0, b, a, y)),
            img.crop((a, b, x, y)),
            img.crop((a, 0, x, b)).transpose(Image.TRANSVERSE)
        )

        paths = []
        s = max(x, y)
        for quad in quadrants:
            path, remainder = img2hilbert(quad, remainder)
            paths.append(path)
        paths[0] = tuple([0*s + y, 0*s + x] for x,y in paths[0])
        paths[1] = tuple([0*s + x, 1*s + y] for x,y in paths[1])
        paths[2] = tuple([1*s + x, 1*s + y] for x,y in paths[2])
        paths[3] = tuple([2*s - y, 1*s - x] for x,y in paths[3])
        align(paths[0], paths[1], 0)
        align(paths[1], paths[2], 1)
        align(paths[2], paths[3], 0)
        return (tuple(flatten(paths)), remainder)

def align(first, second, axis):
    a = first[-1][axis]
    b = second[0][axis]
    if evenness(a) > evenness(b):
        for i in reversed(range(len(first))):
            if first[i][axis] != a: break
            first[i][axis] = b
    elif evenness(a) < evenness(b):
        for i in range(len(second)):
            if second[i][axis] != b: break
            second[i][axis] = a

def evenness(n):
    return n ^ (n - 1)

path, remainder = img2hilbert(img, 0)
pathstr = "M" + " L".join(f"{x},{y}" for x,y in path)

svg = f"""<svg width="{2 * 2**max_depth}" height="{2 * 2**max_depth}" xmlns="http://www.w3.org/2000/svg">
  <path d="{pathstr}" stroke="black" fill="none" stroke-width="0.75" />
</svg>
<!-- Path with {len(path)} nodes, remainder = {remainder}" -->
"""
print(svg)