README
¶
Hilbert 
Go package for mapping values to and from space-filling curves, such as Hilbert, Peano, Morton, Moore, Snake, and Gosper curves.
Note: This project was previously hosted at github.com/google/hilbert but has moved to github.com/bramp/hilbert.
This is not an official Google product (experimental or otherwise), it is just code that happens to be owned by Google.
Supported Curves
| Curve | Visual | Description |
|---|---|---|
| Hilbert | |
Pros: Excellent spatial locality; no large jumps. Cons: Slightly more complex to compute than Morton. Applications: Spatial indexing (e.g., Google Maps), range queries, and texture mapping. |
| Peano |  |
Pros: The original SFC; provides a different granularity. Cons: Limited to power-of-3 dimensions ($3 \times 3, 9 \times 9$, etc.). Applications: Ternary-based data structures and theoretical studies. |
| Morton |  |
Pros: Extremely fast (bit-interleaving). Cons: Poorer locality due to large "jumps." Applications: Database partitioning (e.g., DynamoDB), GPU memory layouts, and high-speed indexing. |
| Moore |  |
Pros: Closed-loop; start and end points are adjacent. Cons: Similar complexity to Hilbert. Applications: Image scanning, cyclic traversals, and sensor path planning. |
| Sierpinski |  |
Pros: Highly symmetrical; continuous closed curve. Cons: Uses a triangular grid. Applications: Traveling Salesman Problem heuristics and parallel grid refinement. |
| Snake |  |
Pros: Simplest possible traversal. Cons: Poor locality; large jumps at the end of rows. Applications: Raster scanning and baseline benchmarks. |
| Gosper |  |
Pros: Fills hexagonal grids; beautiful fractal structure. Cons: Complex mapping; uses base-7 axial coordinates. Applications: Hexagonal data structures, image processing, and simulations. |
How to use
Install:
go get github.com/bramp/hilbert
Example:
import "github.com/bramp/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 examples of how to draw images of these curves, as well as animations of varying sizes.
| Hilbert | Peano |
|---|---|
 |
 |
| Morton | Moore |
 |
 |
| Sierpinski | Snake |
 |
 |
| Gosper | |
 |
To regenerate these images and optimize them, run:
make images
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/bramp/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)
// Create a Morton curve for mapping to and from a 16 by 16 space.
//s, _ := hilbert.NewMorton(16)
// 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 ¶
Examples ¶
Constants ¶
This section is empty.
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.
Functions ¶
This section is empty.
Types ¶
type Gosper ¶
Gosper represents a 2D Gosper curve of order N. The Gosper curve is a space-filling curve on a hexagonal grid. Implements SpaceFilling2D interface.
func NewGosper ¶
NewGosper returns a Gosper space which maps integers to and from the curve. order is the recursive depth. Total hexagons will be 7^order.
func (*Gosper) GetDimensions ¶
GetDimensions returns the width and height of the bounding box for the hexagonal grid.
func (*Gosper) GetGridType ¶
GetGridType returns the geometry of the grid.
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 ¶
NewHilbert returns a Hilbert space which maps integers to and from the curve. n must be a power of two.
func (*Hilbert) GetDimensions ¶
GetDimensions returns the width and height of the 2D space.
func (*Hilbert) GetGridType ¶
GetGridType returns the geometry of the grid.
type Moore ¶
type Moore struct {
Hilbert
}
Moore represents a 2D Moore curve of order N for mapping to and from. The Moore curve is a closed-loop variation of the Hilbert curve. Implements SpaceFilling interface.
func NewMoore ¶
NewMoore returns a Moore space which maps integers to and from the curve. n must be a power of two.
func (*Moore) GetGridType ¶
GetGridType returns the geometry of the grid.
type Morton ¶
type Morton struct {
N int
}
Morton represents a 2D Morton (Z-order) curve of order N for mapping to and from. Implements SpaceFilling interface.
func NewMorton ¶
NewMorton returns a Morton space which maps integers to and from the curve. n must be a power of two.
func (*Morton) GetDimensions ¶
GetDimensions returns the width and height of the 2D space.
func (*Morton) GetGridType ¶
GetGridType returns the geometry of the grid.
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 ¶
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 ¶
GetDimensions returns the width and height of the 2D space.
func (*Peano) GetGridType ¶
GetGridType returns the geometry of the grid.
type Sierpinski ¶
type Sierpinski struct {
N int
}
Sierpinski represents a 2D Sierpinski space of order N for mapping to and from. Implements SpaceFilling interface.
func NewSierpinski ¶
func NewSierpinski(n int) (*Sierpinski, error)
NewSierpinski returns a Sierpinski space which maps integers to and from the curve. n must be a power of two.
func (*Sierpinski) GetCount ¶
func (s *Sierpinski) GetCount() int
GetCount returns the total number of points on the curve.
func (*Sierpinski) GetDimensions ¶
func (s *Sierpinski) GetDimensions() (int, int)
GetDimensions returns the width and height of the 2D space.
func (*Sierpinski) GetGridType ¶
func (s *Sierpinski) GetGridType() GridType
GetGridType returns the geometry of the grid.
func (*Sierpinski) Map ¶
func (s *Sierpinski) 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 Sierpinski curve in a triangular grid, where y is the row index [0, n-1] and x is the triangle index in that row [0, 2y].
func (*Sierpinski) MapInverse ¶
func (s *Sierpinski) MapInverse(x, y int) (t int, err error)
MapInverse transform coordinates on Sierpinski curve from (x,y) to t.
type Snake ¶
type Snake struct {
N int
}
Snake represents a 2D Snake (Boustrophedon) scan of order N. Implements SpaceFilling2D interface.
func (*Snake) GetDimensions ¶
GetDimensions returns the width and height of the 2D space.
func (*Snake) GetGridType ¶
GetGridType returns the geometry of the grid.
type SpaceFilling ¶
type SpaceFilling = SpaceFilling2D
SpaceFilling is an alias for SpaceFilling2D for backward compatibility. Deprecated: Use SpaceFilling2D instead.
type SpaceFilling2D ¶
type SpaceFilling2D 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.
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)
// GetCount returns the total number of points on the curve.
GetCount() int
// GetGridType returns the geometry of the grid.
GetGridType() GridType
}
SpaceFilling2D represents a 2D space-filling curve that can map points from one dimensions to two.
Source Files
Directories