7.2.7.2 Hilbert Space-Filling Curve

(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-coordinates scalar rank)))
                                       ⇒ #t

When treating integers as k fractional bits,

(= scalar (hilbert-coordinates->integer
           (integer->hilbert-coordinates scalar rank k)) 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 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.

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.

7.2.7.3 Gray code

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.

7.2.7.4 Bitwise Lamination

Function: delaminate-list count ks

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)