README
¶
hilbert
Transform N-dimensional points to and from a 1-dimensional Hilbert fractal curve index.
While there has been a number of 2-d & 3-d implementation present online, it's somehow hard to find one that generalizes the notion of Hilbert curves to arbitrary dimensions of hypercube programmatically.
This is helpful (in my personal use-case) for N-dimensional tree variants (B-Tree/R-Tree).
The core algorithm is a port to Golang from the C code in a paper written by John Skilling published in the journal "Programming the Hilbert curve", (c) 2004 American Institute of Physics.
This package was meant to work on large set/s of integers(big.Int).
Usage:
package main
import (
"fmt"
"github.com/jtejido/hilbert"
"math/big"
)
func main() {
fmt.Println("starting at bits = 5, dimension = 2")
sm, err := hilbert.New(5, 2)
if err != nil {
fmt.Println(err)
}
fmt.Println("decode 1074")
arr := sm.Decode(big.NewInt(1074))
fmt.Printf("%v \n", arr)
t := sm.Encode(arr[0], arr[1])
fmt.Println("encode arr[0], arr[1]")
fmt.Println(t)
fmt.Println("decode back to 1074")
arr2 := sm.Decode(t)
fmt.Printf("%v \n", arr2)
}
Floating point data
This library applies to non-negative integer data. To apply it to floating point numbers, you need to do the following:
-
Decide how much resolution in bits you require for each coordinate. The more bits of precision you use, the higher the cost of the transformation.
-
Write methods to perform a two-way mapping from your coordinate system to the non-negative integers. This transform may require shifting and scaling each dimension a different amount in order to yield a desirable distance metric and origin.
Documentation
¶
Overview ¶
Copyright 2019 jtejido
Package hilbert is created to support multidimensional encoding/decoding to/from a Space-Filling Curve http://en.wikipedia.org/wiki/Hilbert_curve
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( ErrNNotPositive = errors.New("Dimension must be greater than zero") ErrBNotPositive = errors.New("Number of bits must be greater than zero") )
Functions ¶
This section is empty.
Types ¶
type Hilbert ¶
type Hilbert struct {
// contains filtered or unexported fields
}
This algorithm is derived from work done by John Skilling and published in "Programming the Hilbert curve". (c) 2004 American Institute of Physics. https://doi.org/10.1063/1.1751381
func (*Hilbert) Decode ¶
Converts an index (distance along the Hilbert Curve from 0) to a point of dimensions defined
Source Files
Directories