Documentation
¶
Overview ¶
Package curve defines space filling curves. A space filling curve is a curve whose range contains the entirety of a finite k-dimensional space. Space filling curves can be used to map between a linear space and a 2D, 3D, or 4D space.
Hilbert Curves ¶
The Hilbert curve is a continuous, space filling curve first described by David Hilbert. The implementation of Hilbert2D is based on example code from the Hilbert curve (Wikipedia). The implementation of Hilbert3D and Hilbert4D are extrapolated from Hilbert2D.
Technically, a Hilbert curve is a continuous, fractal, space-filling curve of infinite length, constructed as the limit of a series of piecewise linear curves. We refer to the kth piecewise linear curve as the k-order Hilbert curve. The first-order 2D Hilbert curve looks like ⊐. The k-order n-dimensional curve can be constructed from 2ⁿ copies of the (k-1) order curve. These (finite) Hilbert curves are iterative/recursive, and the order refers to the iteration number.
The runtime of Space and Curve scales as O(n∙k) where n is the dimension and k is the order. The length of the curve is 2^(n∙k).
Limitations ¶
An n-dimensional, k-order Hilbert curve will not be fully usable if 2ⁿᵏ overflows int (which is dependent on architecture). Len will overflow if n∙k ≥ bits.UintSize-1. Curve will overflow if n∙k > bits.UintSize-1 for some values of v. Space will not overflow, but it cannot be called with values that do not fit in a signed integer, thus only a subset of the curve can be utilized.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrOverflow = errors.New("overflow int")
ErrOverflow is returned (wrapped) by Hilbert curve constructors when the power would cause Len and Pos to overflow.
var ErrUnderflow = errors.New("order is less than 1")
ErrUnderflow is returned by Hilbert curve constructors when the power is less than 1.
Functions ¶
This section is empty.
Types ¶
type Hilbert2D ¶
type Hilbert2D struct {
// contains filtered or unexported fields
}
Hilbert2D is a 2-dimensional Hilbert curve.
func NewHilbert2D ¶
NewHilbert2D constructs a Hilbert2D of the given order. NewHilbert2D returns ErrOverflow (wrapped) if the order would cause Len and Pos to overflow.
func (Hilbert2D) Coord ¶
Coord writes the spatial coordinates of pos to dst and returns it. If dst is nil, Coord allocates a new slice of length 2; otherwise Coord is allocation-free.
Coord panics if dst is not nil and len(dst) is not equal to 2.
func (Hilbert2D) Dims ¶
Dims returns the spatial dimensions of the curve, which is {2ᵏ, 2ᵏ}, where k is the order.
func (Hilbert2D) Len ¶
Len returns the length of the curve, which is 2ⁿᵏ, where n is the dimension (2) and k is the order.
Len will overflow if order is ≥ 16 on architectures where [int] is 32-bits, or ≥ 32 on architectures where [int] is 64-bits.
func (Hilbert2D) Pos ¶
Pos returns the linear position of the 3-spatial coordinate v along the curve. Pos modifies v.
Pos will overflow if order is ≥ 16 on architectures where [int] is 32-bits, or ≥ 32 on architectures where [int] is 64-bits.
Example ¶
h := Hilbert2D{order: 3}
for y := 0; y < 1<<h.order; y++ {
for x := 0; x < 1<<h.order; x++ {
if x > 0 {
fmt.Print(" ")
}
fmt.Printf("%02x", h.Pos([]int{x, y}))
}
fmt.Println()
}
Output: 00 01 0e 0f 10 13 14 15 03 02 0d 0c 11 12 17 16 04 07 08 0b 1e 1d 18 19 05 06 09 0a 1f 1c 1b 1a 3a 39 36 35 20 23 24 25 3b 38 37 34 21 22 27 26 3c 3d 32 33 2e 2d 28 29 3f 3e 31 30 2f 2c 2b 2a
type Hilbert3D ¶
type Hilbert3D struct {
// contains filtered or unexported fields
}
Hilbert3D is a 3-dimensional Hilbert curve.
func NewHilbert3D ¶
NewHilbert3D constructs a Hilbert3D of the given order. NewHilbert3D returns ErrOverflow (wrapped) if the order would cause Len and Pos to overflow.
func (Hilbert3D) Coord ¶
Coord writes the spatial coordinates of pos to dst and returns it. If dst is nil, Coord allocates a new slice of length 3; otherwise Coord is allocation-free.
Coord panics if dst is not nil and len(dst) is not equal to 3.
func (Hilbert3D) Dims ¶
Dims returns the spatial dimensions of the curve, which is {2ᵏ, 2ᵏ, 2ᵏ}, where k is the order.
func (Hilbert3D) Len ¶
Len returns the length of the curve, which is 2ⁿᵏ, where n is the dimension (3) and k is the order.
Len will overflow if order is ≥ 11 on architectures where [int] is 32-bits, or ≥ 21 on architectures where [int] is 64-bits.
func (Hilbert3D) Pos ¶
Pos returns the linear position of the 4-spatial coordinate v along the curve. Pos modifies v.
Pos will overflow if order is ≥ 11 on architectures where [int] is 32-bits, or ≥ 21 on architectures where [int] is 64-bits.
Example ¶
h := Hilbert3D{order: 2}
for z := 0; z < 1<<h.order; z++ {
for y := 0; y < 1<<h.order; y++ {
for x := 0; x < 1<<h.order; x++ {
if x > 0 {
fmt.Print(" ")
}
fmt.Printf("%02x", h.Pos([]int{x, y, z}))
}
fmt.Println()
}
fmt.Println()
}
Output: 00 07 08 0b 01 06 0f 0c 1a 1b 10 13 19 18 17 14 03 04 09 0a 02 05 0e 0d 1d 1c 11 12 1e 1f 16 15 3c 3b 36 35 3d 3a 31 32 22 23 2e 2d 21 20 29 2a 3f 38 37 34 3e 39 30 33 25 24 2f 2c 26 27 28 2b
type Hilbert4D ¶
type Hilbert4D struct {
// contains filtered or unexported fields
}
Hilbert4D is a 4-dimensional Hilbert curve.
func NewHilbert4D ¶
NewHilbert4D constructs a Hilbert4D of the given order. NewHilbert4D returns ErrOverflow (wrapped) if the order would cause Len and Pos to overflow.
func (Hilbert4D) Coord ¶
Coord writes the spatial coordinates of pos to dst and returns it. If dst is nil, Coord allocates a new slice of length 4; otherwise Coord is allocation-free.
Coord panics if dst is not nil and len(dst) is not equal to 4.
func (Hilbert4D) Dims ¶
Dims returns the spatial dimensions of the curve, which is {2ᵏ, 2ᵏ, 2ᵏ, 2ᵏ}, where k is the order.
func (Hilbert4D) Len ¶
Len returns the length of the curve, which is 2ⁿᵏ, where n is the dimension (4) and k is the order.
Len will overflow if order is ≥ 8 on architectures where [int] is 32-bits, or ≥ 16 on architectures where [int] is 64-bits.
func (Hilbert4D) Pos ¶
Pos returns the linear position of the 2-spatial coordinate v along the curve. Pos modifies v.
Pos will overflow if order is ≥ 8 on architectures where [int] is 32-bits, or ≥ 16 on architectures where [int] is 64-bits.
Example ¶
h := Hilbert4D{order: 2}
N := 1 << h.order
for z := 0; z < N; z++ {
if z > 0 {
s := strings.Repeat("═", N*4-2)
s = s + strings.Repeat("═╬═"+s, N-1)
fmt.Println(s)
}
for y := 0; y < N; y++ {
for w := 0; w < N; w++ {
if w > 0 {
fmt.Print(" ║ ")
}
for x := 0; x < N; x++ {
if x > 0 {
fmt.Print(" ")
}
fmt.Printf("%02x", h.Pos([]int{x, y, z, w}))
}
}
fmt.Println()
}
}
Output: 00 0f 10 13 ║ 03 0c 11 12 ║ fc f3 ee ed ║ ff f0 ef ec 01 0e 1f 1c ║ 02 0d 1e 1d ║ fd f2 e1 e2 ║ fe f1 e0 e3 32 31 20 23 ║ 35 36 21 22 ║ ca c9 de dd ║ cd ce df dc 33 30 2f 2c ║ 34 37 2e 2d ║ cb c8 d1 d2 ║ cc cf d0 d3 ═══════════════╬════════════════╬════════════════╬═══════════════ 07 08 17 14 ║ 04 0b 16 15 ║ fb f4 e9 ea ║ f8 f7 e8 eb 06 09 18 1b ║ 05 0a 19 1a ║ fa f5 e6 e5 ║ f9 f6 e7 e4 3d 3e 27 24 ║ 3a 39 26 25 ║ c5 c6 d9 da ║ c2 c1 d8 db 3c 3f 28 2b ║ 3b 38 29 2a ║ c4 c7 d6 d5 ║ c3 c0 d7 d4 ═══════════════╬════════════════╬════════════════╬═══════════════ 76 77 6c 6d ║ 79 78 6b 6a ║ 86 87 94 95 ║ 89 88 93 92 75 74 63 62 ║ 7a 7b 64 65 ║ 85 84 9b 9a ║ 8a 8b 9c 9d 42 41 5c 5d ║ 45 46 5b 5a ║ ba b9 a4 a5 ║ bd be a3 a2 43 40 53 52 ║ 44 47 54 55 ║ bb b8 ab aa ║ bc bf ac ad ═══════════════╬════════════════╬════════════════╬═══════════════ 71 70 6f 6e ║ 7e 7f 68 69 ║ 81 80 97 96 ║ 8e 8f 90 91 72 73 60 61 ║ 7d 7c 67 66 ║ 82 83 98 99 ║ 8d 8c 9f 9e 4d 4e 5f 5e ║ 4a 49 58 59 ║ b5 b6 a7 a6 ║ b2 b1 a0 a1 4c 4f 50 51 ║ 4b 48 57 56 ║ b4 b7 a8 a9 ║ b3 b0 af ae
Source Files