The code in intbert.c
computes the position of n-th "node" of the 2D Hilbert
curve in O(1) time, using only bitwise integer operation.
The method is loosely based on transforming the U-curve (aka Gray code) with consecutive accumulated rotations and flips, then deinterleaving (as in Morton Z-curve).
To run a demo (order 14 curve):
make intbert
./intbert 14 > hilbert14.tsv
To plot the results (here using R
):
d <- read.table('hilbert14.tsv')[,3:4]
# plot interactively
plot(d, pch=20, cex=.5, col=rainbow(2^14))
lines(d)
# plot to SVG
svg('hilbert14.svg', 20, 20)
plot(d, type='l', lwd=2, xlab='', ylab='')
points(d, pch=20, col=rainbow(2^14))
dev.off()
TODOs:
- reverse transform (2D coords to 1D Hilbert)
- optimized versions (x86 asm, shaders, lower-than-64bit versions, ...)
Public domain.
(But I'll be happy if you link back to this repo.)