Recently I wanted to generate hilbert curve indexing of 2D array as a part of one experiment. The experiment wasn't very successful itself, but I found the resulting Python code for curve generation prety neat to post it.
Here are a couple of interesting references on space-filling curve construction and theis applications:
So let's write some code!
def hilbert_curve(n): ''' Generate Hilbert curve indexing for (n, n) array. 'n' must be a power of two. ''' # recursion base if n == 1: return zeros((1, 1), int32) # make (n/2, n/2) index t = hilbert_curve(n//2) # flip it four times and add index offsets a = flipud(rot90(t)) b = t + t.size c = t + t.size*2 d = flipud(rot90(t, -1)) + t.size*3 # and stack four tiles into resulting array return vstack(map(hstack, [[a, b], [d, c]]))
That's it. Lets try some small n values.
[[0 1] [3 2]]
[[ 0 3 4 5] [ 1 2 7 6] [14 13 8 9] [15 12 11 10]]
Now let's show the generated indices with color. Note, how nearby cells tend to have close indices. That's why such curves are useful for spatial indexing.
Ok, time to plot the curve itself.
idx = hilbert_curve(32) y, x = indices(idx.shape).reshape(2, -1) x[idx.ravel()], y[idx.ravel()] = x.copy(), y.copy() plot(x, y) axis('equal') axis('off') _=ylim(ymin=-1)
This post in generated from IPython Notebook, which can be found in my GitHub repository