Data.Algorithm.Hilbert

Author: CJ East [e-mail] Stability: experimental Portability: Portable

Conversion to-and-from points in a Hilbert space, based on the paper:

Hamilton, C. Compact Hilbert Indices - Technical Report -- CS-2006-07

At the time of writing, the paper can be found at: https://www.cs.dal.ca/sites/default/files/technical_reports/CS-2006-07.pdf

Hilbert Curve Functions

pointToIndex

Arguments

:: Integral u

=> Int

The order of the Hilbert curve.

-> Int

The dimension of the Hilbert curve.

-> [u]

A list specifying a point in the Hilbert space

-> Maybe u

The resulting Hilbert index.

pointToIndex takes a point in n-dimensional space, and returns the Hilbert index of that point.

A two-dimensional Hilbert Curve is shown at XKCD, which we'll use to illustrate how this module works.

That diagram is a two dimensional Hilbert curve, tiled 16 x 16, more specifically, it has order equal to logBase 2 16 = 4 This library solves a simple problem - if you wanted to make a similar a digram, how would you calculate which octet should occur in the upper right corner of each square, given the co-ordinates of each square?

The pointToIndex function determines pointToIndex order dimension point For the top-left corner.

 pointToIndex 4 2 [0, 0] = 0  

For the bottom-right corner;

 pointToIndex 4 2 [15, 15] = 170 

For MIT, at co-ordinates x = 5, y = 1 relative to the top left corner.

 pointToIndex 4 2 [1 , 5]  
= 18

indexToPoint

Arguments

:: (Integral u, Num u)

=> Int

The order of the Hilbert curve.

-> Int

The dimension of the Hilbert curve.

-> u

An index in the Hilbert space

-> Maybe [u]

The resulting Hilbert point.

indexToPoint provides the inverse mapping for pointToIndex.

Adopting the example from pointToIndex above:

indexToPoint 4 2 18  
= [1,5]

Another use for indexToPoint is to create a (roughly) continuous RGB palette from a one dimensional interval, for use in data visualisation. For this application, assuming RGB with an 8 bit color depth on each component, we need:

order = logBase 2 256 = 8

dimension = 3

We can now calculate the RGB color corresponding to any number in the interval 0 .. (2^24)-1

indexToPoint 8 3 167
= [1,7,7]

indexToPoint 8 3 1000
[10,0,4]

Gray Code Functions

grayCode :: PrecisionNum -> PrecisionNum

Generate the ith binary reflected graycode given i. See Theorem 2.1 of Hamilton.

grayCodeInverse :: PrecisionNum -> PrecisionNum

Generate i given the ith binary reflected graycode.