Next: Peano Space-Filling Curve, Previous: Multidimensional Space-Filling Curves, Up: Space-Filling Curves [Contents][Index]
The Hilbert Space-Filling Curve is a one-to-one mapping between a unit line segment and an n-dimensional unit cube. This implementation treats the nonnegative integers either as fractional bits of a given width or as nonnegative integers.
The integer procedures map the non-negative integers to an arbitrarily large n-dimensional cube with its corner at the origin and all coordinates are non-negative.
For any exact nonnegative integer scalar and exact integer rank > 2,
(= scalar (hilbert-coordinates->integer (integer->hilbert-coordinates scalar rank))) ⇒ #t
When treating integers as k fractional bits,
(= scalar (hilbert-coordinates->integer (integer->hilbert-coordinates scalar rank k)) k) ⇒ #t
Returns a list of rank integer coordinates corresponding to exact
non-negative integer scalar. The lists returned by integer->hilbert-coordinates
for scalar arguments
0 and 1 will differ in the first element.
scalar must be a nonnegative integer of no more than
rank*k
bits.
integer->hilbert-coordinates
Returns a list of rank k-bit nonnegative integer
coordinates corresponding to exact non-negative integer scalar. The
curves generated by integer->hilbert-coordinates
have the same alignment independent of
k.
Returns an exact non-negative integer corresponding to coords, a list of non-negative integer coordinates.
A Gray code is an ordering of non-negative integers in which exactly one bit differs between each pair of successive elements. There are multiple Gray codings. An n-bit Gray code corresponds to a Hamiltonian cycle on an n-dimensional hypercube.
Gray codes find use communicating incrementally changing values between asynchronous agents. De-laminated Gray codes comprise the coordinates of Hilbert space-filling curves.
Converts k to a Gray code of the same integer-length
as
k.
Converts the Gray code k to an integer of the same
integer-length
as k.
For any non-negative integer k,
(eqv? k (gray-code->integer (integer->gray-code k)))
These procedures return #t if their Gray code arguments are (respectively): equal, monotonically increasing, monotonically decreasing, monotonically nondecreasing, or monotonically nonincreasing.
For any non-negative integers k1 and k2, the Gray code
predicate of (integer->gray-code k1)
and
(integer->gray-code k2)
will return the same value as the
corresponding predicate of k1 and k2.
Returns a list of count integers comprised of the jth bit of the integers ks where j ranges from count-1 to 0.
(map (lambda (k) (number->string k 2)) (delaminate-list 4 '(7 6 5 4 0 0 0 0))) ⇒ ("0" "11110000" "11000000" "10100000")
delaminate-list
is its own inverse:
(delaminate-list 8 (delaminate-list 4 '(7 6 5 4 0 0 0 0))) ⇒ (7 6 5 4 0 0 0 0)
Next: Peano Space-Filling Curve, Previous: Multidimensional Space-Filling Curves, Up: Space-Filling Curves [Contents][Index]