hilbert-0.0.0.1: Calculate points on an arbitrary Hilbert curve

Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.Algorithm.Hilbert.Functions

Synopsis

Documentation

pointToIndex Source

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 Source

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]

grayCode :: PrecisionNum -> PrecisionNum Source

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

grayCodeInverse :: PrecisionNum -> PrecisionNum Source

Generate i given the ith binary reflected graycode.

newD :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum Source

Helper function for calculation of pointToIndex and indexToPoint. See Hamilton, Algorithm 2 and Algorithm 3.

newE :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum Source

Helper function for calculation of pointToIndex and indexToPoint. See Hamilton, Algorithm 2 and Algorithm 3. FIXME: dimension is unused.