hilbert-0.0.0.1: Calculate points on an arbitrary Hilbert curve

Data.Algorithm.Hilbert.Functions

Synopsis

# Documentation

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```

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]```

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

Generate i given the ith binary reflected graycode.

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

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