Safe Haskell	Safe-Inferred
Language	Haskell2010

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

pointToIndex' :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum -> [PrecisionNum] -> Maybe PrecisionNum Source

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]

indexToPoint' :: PrecisionNum -> PrecisionNum -> PrecisionNum -> PrecisionNum -> [PrecisionNum] -> [Maybe PrecisionNum] Source

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.