API Reference

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.

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.

• Hamilton, Chris H., and Andrew Rau-Chaplin. "Compact Hilbert indices for multi-dimensional data." First International Conference on Complex, Intelligent and Software Intensive Systems (CISIS'07). IEEE, 2007.

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.

For developers, note that this algorithm relies on encoding the Hilbert index in what, to me, was a surprising order. To understand the interleaving of the Hilbert index for this algorithm, start with a 2D value where higher bits are larger subscripts, $(a_4a_3a_2a_1, b_4b_3b_2b_1)$. Skilling encodes this as $a_4b_4a_3b_3a_2b_2a_1b_1$, which looks good on paper, but it means the first element of the vector has the higher bits.

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

• Butz, Arthur R. "Alternative algorithm for Hilbert's space-filling curve." IEEE Transactions on Computers 100.4 (1971): 424-426.
• Lawder, Jonathan K. "Calculation of mappings between one and n-dimensional values using the hilbert space-filling curve." School of Computer Science and Information Systems, Birkbeck College, University of London, London Research Report BBKCS-00-01 August (2000).

Compact{T,B}(m::AbstractVector{<:Integer})
Compact(T, m::AbstractVector{<:Integer})
Compact(m::AbstractVector{<:Integer})

Compact Hilbert curve algorithm for anisotropic grids where each axis can have a different number of bits. If you don't specify type parameters they are chosen for you depending on the size of m.

Type Parameters

• T - Hilbert index type (e.g., UInt64, UInt128)
• B - Coordinate type (e.g., UInt32)

Arguments

• m - Vector of bit counts, one per axis

Example

c = Compact{UInt64, UInt32}([3, 2, 4])  # Dimension [2^3, 2^2, 2^4]
h = encode_hilbert_zero(c, UInt32[5, 2, 11])

This code starts with the tech report and paper by Chris Hamilton. That paper and subsequent versions make a Hilbert curve for unequal side lengths without a guarantee that consecutive points are adjacent. This code will always produce a lattice-continuous Hilbert curve.

Hamilton, Chris. "Compact hilbert indices." Dalhousie University, Faculty of Computer Science, Technical Report CS-2006-07 (2006).

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.

decode_hilbert!(ha::HilbertAlgorithm{T}, X::Vector{A})

A 1-based Hilbert decode, from decode_hilbert_zero!. Both the Hilbert index and the axes start counting at 1 instead of 0.

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.

encode_hilbert_zero(c::Compact, X)

Encode a point X (0-based coordinates) to a Hilbert index (0-based).

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.

decode_hilbert_zero!(c::Compact, X, h)

Decode a Hilbert index h (0-based) to point X (0-based coordinates).