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.

— 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.2 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.3 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)

7.2.7.1 Hilbert Space-Filling Curve

7.2.7.2 Gray code

7.2.7.3 Bitwise Lamination