Next: Peano Space-Filling Curve, Previous: Multidimensional Space-Filling Curves, Up: Space-Filling Curves

`(require 'hilbert-fill)`

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

rankinteger coordinates corresponding to exact non-negative integerscalar. The lists returned by`integer->hilbert-coordinates`

forscalararguments 0 and 1 will differ in the first element.

— Function: **integer->hilbert-coordinates**` scalar rank k`

scalarmust be a nonnegative integer of no more thanrank`*`

kbits.

`integer->hilbert-coordinates`

Returns a list ofrankk-bit nonnegative integer coordinates corresponding to exact non-negative integerscalar. The curves generated by`integer->hilbert-coordinates`

have the same alignment independent ofk.

— Function: **hilbert-coordinates->integer**` coords`

— Function:**hilbert-coordinates->integer**` coords k`

— Function:

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: **gray-code->integer**` k`

Converts the Gray code

kto an integer of the same`integer-length`

ask.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`

— Function:

— Function:

— Function:

— Function:

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

k1andk2, the Gray code predicate of`(integer->gray-code k1)`

and`(integer->gray-code k2)`

will return the same value as the corresponding predicate ofk1andk2.

— Function: **delaminate-list**` count ks`

Returns a list of

countintegers comprised of thejth bit of the integerskswherejranges fromcount-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)