Skip to content

Instantly share code, notes, and snippets.

@vyznev
Created June 9, 2021 21:21
Show Gist options
  • Save vyznev/afe31bcfd03073a16d32240fcc7cb7b8 to your computer and use it in GitHub Desktop.
Save vyznev/afe31bcfd03073a16d32240fcc7cb7b8 to your computer and use it in GitHub Desktop.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment