hilbert

README

Hilbert

Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves.

Documentation available here

This is not an official Google product (experimental or otherwise), it is just code that happens to be owned by Google.

How to use

Install:

go get github.com/google/hilbert

Example:

import "github.com/google/hilbert"
	
// Create a Hilbert curve for mapping to and from a 16 by 16 space.
s, err := hilbert.NewHilbert(16)

// Create a Peano curve for mapping to and from a 27 by 27 space.
//s, err := hilbert.NewPeano(27)

// Now map one dimension numbers in the range [0, N*N-1], to an x,y
// coordinate on the curve where both x and y are in the range [0, N-1].
x, y, err := s.Map(t)

// Also map back from (x,y) to t.
t, err := s.MapInverse(x, y)

Demo

The demo directory contains an example on how to draw an images of Hilbert and Peano curves, as well as animations of varying sizes for both.

go run $GOPATH/src/github.com/google/hilbert/demo/demo.go

and the following images are generated.

Simple 8x8 Hibert curve:

Simple 9x9 Peano curve:

Animation of Hibert curve with N in the range 1..8:

Animation of Peano curve with N in the range 1..6:

Licence (Apache 2)

Copyright 2015 Google Inc. All Rights Reserved.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

Documentation

Overview

Package hilbert is for mapping values to and from space-filling curves, such as Hilbert and Peano curves.

Example

package main

import (
	"fmt"

	"github.com/google/hilbert"
)

func main() {

	// Create a Hilbert curve for mapping to and from a 16 by 16 space.
	s, _ := hilbert.NewHilbert(16)

	// Create a Peano curve for mapping to and from a 27 by 27 space.
	//s, _ := hilbert.NewPeano(27)

	// Now map one dimension numbers in the range [0, N*N-1], to an x,y
	// coordinate on the curve where both x and y are in the range [0, N-1].
	x, y, _ := s.Map(96)

	// Also map back from (x,y) to t.
	t, _ := s.MapInverse(x, y)

	fmt.Printf("x = %d, y = %d, t = %d\n", x, y, t)

}

Output:

x = 4, y = 12, t = 96

Index

• Variables
• type Hilbert
  • func NewHilbert(n int, verticalCompatible bool) (*Hilbert, error)
  • func (s *Hilbert) GetDimensions() (int, int)
  • func (s *Hilbert) Map(t int) (x, y int, err error)
  • func (s *Hilbert) MapInverse(x, y int) (t int, err error)
• type Peano
  • func NewPeano(n int) (*Peano, error)
  • func (p *Peano) GetDimensions() (int, int)
  • func (p *Peano) Map(t int) (x, y int, err error)
  • func (p *Peano) MapInverse(x, y int) (t int, err error)
• type SpaceFilling

Examples

• Package

Variables

var (
	ErrNotPositive     = errors.New("N must be greater than zero")
	ErrNotPowerOfTwo   = errors.New("N must be a power of two")
	ErrNotPowerOfThree = errors.New("N must be a power of three")
	ErrOutOfRange      = errors.New("value is out of range")
)

Errors returned when validating input.

Types

type Hilbert

type Hilbert struct {
	N int
	// contains filtered or unexported fields
}

Hilbert represents a 2D Hilbert space of order N for mapping to and from. Implements SpaceFilling interface.

func NewHilbert

func NewHilbert(n int, verticalCompatible bool) (*Hilbert, error)

NewHilbert returns a Hilbert space which maps integers to and from the curve. n must be a power of two. If verticalCompatible is true, the Hilbert curve will be rotated 90 degrees and rotated around the Y-axis. In other words instead of the Hilbert curve representing the shaper of the letter U, it will look like a backwards letter C. This allows multiple square Hilbert curves to be vertically stacked and maintain the Hilbert locality property.

func (*Hilbert) GetDimensions

func (s *Hilbert) GetDimensions() (int, int)

GetDimensions returns the width and height of the 2D space.

func (*Hilbert) Map

func (s *Hilbert) Map(t int) (x, y int, err error)

Map transforms a one dimension value, t, in the range [0, n^2-1] to coordinates on the Hilbert curve in the two-dimension space, where x and y are within [0,n-1].

func (*Hilbert) MapInverse

func (s *Hilbert) MapInverse(x, y int) (t int, err error)

MapInverse transform coordinates on Hilbert curve from (x,y) to t.

type Peano

type Peano struct {
	N int // Always a power of three, and is the width/height of the space.
}

Peano represents a 2D Peano curve of order N for mapping to and from. Implements SpaceFilling interface.

func NewPeano

func NewPeano(n int) (*Peano, error)

NewPeano returns a new Peano space filling curve which maps integers to and from the curve. n must be a power of three.

func (*Peano) GetDimensions

func (p *Peano) GetDimensions() (int, int)

GetDimensions returns the width and height of the 2D space.

func (*Peano) Map

func (p *Peano) Map(t int) (x, y int, err error)

Map transforms a one dimension value, t, in the range [0, n^3-1] to coordinates on the Peano curve in the two-dimension space, where x and y are within [0,n-1].

func (*Peano) MapInverse

func (p *Peano) MapInverse(x, y int) (t int, err error)

MapInverse transform coordinates on the Peano curve from (x,y) to t. NOT IMPLEMENTED YET

type SpaceFilling

type SpaceFilling interface {
	// Map transforms a one dimension value, t, in the range [0, n^2-1] to coordinates on the
	// curve in the two-dimension space, where x and y are within [0,n-1].
	Map(t int) (x, y int, err error)

	// MapInverse transform coordinates on the curve from (x,y) to t.
	MapInverse(x, y int) (t int, err error)

	// GetDimensions returns the width and height of the 2D space.
	GetDimensions() (x, y int)
}

SpaceFilling represents a space-filling curve that can map points from one dimensions to two.