GitHub

Usage

Create an encoder

    simple = Simple2D(HilbertType)
    sg = SpaceGray(HilbertType, bits, dimensions)
    gg = GlobalGray(HilbertType, bits, dimensions)
    sg = FaceContinuous(HilbertType, bits, dimensions)

  • HilbertType is an unsigned integer DataType large enough to hold the HilbertIndex. The returned HilbertIndex will have this type. Examples are UInt32 and UInt128.

  • bits is the maximum bit width of a DataType that can hold the Cartesian index in each dimension. If bits is 7, that means all indices are between 1 and 128=2^7 or between 0 and 127=2^7-1.

  • dimension is the integer number of Cartesian dimensions.

Simple2D doesn't need to know dimensions ahead of time.

Encode and Decode

    hilbert_index = encode_hilbert(encoder, cartesian::AbstractVector)
    decode_hilbert!(encoder, cartesian, hilbert_index)

This converts from Cartesian indices in a vector to an integer Hilbert index. Then it converts back to Cartesian. decoding overwrites the cartesian array values. The input Cartesian vector may have any AbstractVector type. It can be faster if you use a StaticArrays.MVector of fixed size.

    hilbert_index = encode_hilbert_zero(encoder, cartesian::AbstractVector)
    decode_hilbert_zero!(encoder, cartesian, hilbert_index)

These are the same as above, but they use zero-based indices. The one-based are a layer on top of these zero-based implementations.

Example bit calculations

If the Hilbert curve will be in a 32 x 32 space, then the dimension is 2, and it needs log2(32)=5 bits of resolution in both directions. For GlobalGray, that's b=5, n=2. If the sizes aren't powers of two or are uneven, then set the bits to cover the largest side, so (12 x 12 x 12 x 800) would be b=10, n=4 because $800 < 2^{10}$.

Index

BijectiveHilbert.Bijective.Simple2D — Type

Simple2D(::Type{T})

The type is a data type to hold the Hilbert index. It should have enough bits to hold all bits of integer axes to encode.

The variant algorithm used differs from the usual Hilbert code because it doesn't need to know the size of the whole grid before computing the code. It looks like a slightly-rotated version of the Hilbert curve, but it has the benefit that it is 1-1 between (x, y) and z, so you can translate back and forth.

If the size of the axis values or the size of the Hilbert index are too large to be stored in the data types of the axis vector or index, then you'll see an error from a failure of trunc, which tries to copy values into the smaller datatype. Solve this by using a larger datatype, so UInt64 instead of UInt32.

It comes from a paper: N. Chen, N. Wang, B. Shi, A new algorithm for encoding and decoding the Hilbert order. Software—Practice and Experience 2007; 37(8): 897–908.

source
BijectiveHilbert.FaceContinuous — Type
FaceContinuous(b::Int, n::Int)
FaceContinuous(::Type{T}, b::Int, n::Int)

For n dimensions, use b bits of precision in this Hilbert curve. If you specify a type T, this will be used as the type of the Hilbert encoding. If not, the smallest unsigned integer that can hold n*b bits will be used for the Hilbert index data type.

This is the Butz algorithm, as presented by Lawder. Haverkort2017 says it is face continuous. The code is in lawder.c. The original paper had an error, and Lawder put a correction on his website. http://www.dcs.bbk.ac.uk/~jkl/publications.html

source
BijectiveHilbert.GlobalGray — Type
GlobalGray(b, n)
GlobalGray(T, b, n)

T is a data type for the Hilbert index. It can be signed or unsigned, as long as it has at least n * b bits. n is the number of dimensions, and b is the bits per dimension, so each axis value should be between 0 and $2^b - 1$, inclusive, for the zero-based interface. They should be between 1 and $2^b$, inclusive, for the one-based interface.

The GlobalGray algorithm is an n-dimensional Hilbert curve with a simplified implementation. It follows an article, "Programming the Hilbert Curve," by John Skilling, 707 (2004), http://dx.doi.org/10.1063/1.1751381. I call it "Global Gray" because the insight of the article is that a single, global Gray code can be applied to all np bits of a Hilbert length.

source
BijectiveHilbert.SpaceGray — Type
SpaceGray(b, n)
SpaceGray(::Type{T}, b, n)

This is an n-dimensional Hilbert curve where all n dimensions must have b bits in size. It was described in the same paper and examples as the Compact algorithm.

source
BijectiveHilbert.decode_hilbert_zero! — Method
decode_hilbert_zero!(ha::HilbertAlgorithm{T}}, X::Vector{A}, h::T)

Given a Hilbert index, h, computes an n-dimensional coordinate X. The type of the Hilbert index is large enought to contain the bits of all dimensions of the axis vector, X.

source
BijectiveHilbert.encode_hilbert — Method
encode_hilbert(ha::HilbertAlgorithm{T}, X::Vector{A})

A 1-based Hilbert encoding. Both the Hilbert index and the axes start counting at 1 instead of 0.

source
BijectiveHilbert.encode_hilbert_zero — Method
encode_hilbert_zero(ha::HilbertAlgorithm{T}, X::Vector{A})

Takes an n-dimensional vector X and returns a single integer of type T which orders X to improve spatial locality. The input X has multiple axes and the output is called a Hilbert index. This version is zero-based, so each axis counts from 0, and the smallest Hilbert index is 0.

source