Copyright | © 2013-2015 CJ East |
---|---|

License | BSD3 |

Maintainer | CJ East <cje@ieee.org> |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

Author: CJ East cje@ieee.org 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

- pointToIndex :: Integral u => Int -> Int -> [u] -> Maybe u
- indexToPoint :: (Integral u, Num u) => Int -> Int -> u -> Maybe [u]
- grayCode :: PrecisionNum -> PrecisionNum
- grayCodeInverse :: PrecisionNum -> PrecisionNum

# Hilbert Curve Functions

:: Integral u | |

=> Int | The |

-> Int | The |

-> [u] | A list specifying a |

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

:: (Integral u, Num u) | |

=> Int | The |

-> Int | The |

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