hilbert

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:

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

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

• Variables
• type Hilbert
  • func New(b, n uint32) (*Hilbert, error)
  • func (s *Hilbert) Bits() uint32
  • func (s *Hilbert) Decode(index *big.Int) []uint64
  • func (s *Hilbert) Dimension() uint32
  • func (s *Hilbert) Encode(x ...uint64) *big.Int
  • func (s *Hilbert) Len() uint32

Variables

var (
	ErrNNotPositive = errors.New("Dimension must be greater than zero")
	ErrBNotPositive = errors.New("Number of bits must be greater than zero")
)

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 New

func New(b, n uint32) (*Hilbert, error)

func (*Hilbert) Bits

func (s *Hilbert) Bits() uint32

The number of bits

func (*Hilbert) Decode

func (s *Hilbert) Decode(index *big.Int) []uint64

Converts an index (distance along the Hilbert Curve from 0) to a point of dimensions defined

func (*Hilbert) Dimension

func (s *Hilbert) Dimension() uint32

The number of dimensions

func (*Hilbert) Encode

func (s *Hilbert) Encode(x ...uint64) *big.Int

Converts points to its Hilbert curve index.

func (*Hilbert) Len

func (s *Hilbert) Len() uint32

The number of length