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-coordinatesscalarrank))) ⇒ #t

When treating integers as `k` fractional bits,

(=scalar(hilbert-coordinates->integer (integer->hilbert-coordinatesscalarrankk))k) ⇒ #t

- Function:
**integer->hilbert-coordinates***scalar rank* -
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.

- Function:
**integer->hilbert-coordinates***scalar rank k* -
`scalar`must be a nonnegative integer of no more than

bits.`rank`*`k``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`.

- Function:
**hilbert-coordinates->integer***coords* - Function:
**hilbert-coordinates->integer***coords 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.

- Function:
**integer->gray-code***k* Converts

`k`to a Gray code of the same`integer-length`

as`k`.

- Function:
**gray-code->integer***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)))

- Function:
**=***k1 k2* - Function:
**gray-code<?***k1 k2* - Function:
**gray-code>?***k1 k2* - Function:
**gray-code<=?***k1 k2* - Function:
**gray-code>=?***k1 k2* 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`.

- Function:
**delaminate-list***count ks* -
Returns a list of

`count`integers comprised of the`j`th 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)