README

Hilbert Build Status Coverage Report card GoDoc Libraries.io

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

Image of 8 by 8 Hilbert curve

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:

8x8 Hilbert curve image

Simple 9x9 Peano curve:

9x9 Hilbert curve image

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

Hilbert curve animation

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

Peano curve animation

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
    Output:
    
    x = 4, y = 12, t = 96
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

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

      Functions

      This section is empty.

      Types

      type Hilbert

      type Hilbert struct {
      	N int
      }

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

        func NewHilbert

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

          NewHilbert returns a Hilbert space which maps integers to and from the curve. n must be a power of two.

          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.

                            Directories

                            Path Synopsis
                            Package main is a simple demo to show how to use the hilbert library When ran, this demo will create the following images: hilbert.png, hilbert_animation.gif, peano.png, and peano_animation.gif It is suggested you optimise/compress both images before uploading.
                            Package main is a simple demo to show how to use the hilbert library When ran, this demo will create the following images: hilbert.png, hilbert_animation.gif, peano.png, and peano_animation.gif It is suggested you optimise/compress both images before uploading.
                            lib