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.
| 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 ( 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. |
Install:
go get github.com/bramp/hilbertExample:
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)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 imagesCopyright 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.