Next: , Previous: , Up: Space-Filling Curves   [Contents][Index]

#### 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)
```

Next: , Previous: , Up: Space-Filling Curves   [Contents][Index]