Module: Geospatial::Hilbert
- Defined in:
- lib/geospatial/hilbert.rb,
lib/geospatial/hilbert/curve.rb,
lib/geospatial/hilbert/traverse.rb
Defined Under Namespace
Classes: Curve
Class Method Summary collapse
-
.map(hilbert_axes, bits) ⇒ Object
Given the coordinates of a point in N-Dimensional space, find the distance to that point along the Hilbert curve.
-
.unmap(transposed_index, bits) ⇒ Object
Convert the Hilbert index into an N-dimensional point expressed as a vector of uints.
Class Method Details
.map(hilbert_axes, bits) ⇒ Object
Given the coordinates of a point in N-Dimensional space, find the distance to that point along the Hilbert curve. That distance will be transposed; broken into pieces and distributed into an array.
The number of dimensions is the length of the hilbert_index array.
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
# File 'lib/geospatial/hilbert.rb', line 83 def self.map(hilbert_axes, bits) x = hilbert_axes.dup n = x.length # n: Number of dimensions m = 1 << (bits - 1) # Inverse undo q = m while q > 1 p = q - 1 i = 0 while i < n if (x[i] & q) != 0 x[0] ^= p # invert else t = (x[0] ^ x[i]) & p; x[0] ^= t; x[i] ^= t; end i += 1 end q >>= 1 end # exchange # Gray encode 1.upto(n-1) {|i| x[i] ^= x[i-1]} t = 0 q = m while q > 1 if x[n-1] & q != 0 t ^= q - 1 end q >>= 1 end 0.upto(n-1) {|i| x[i] ^= t} return x end |
.unmap(transposed_index, bits) ⇒ Object
Convert the Hilbert index into an N-dimensional point expressed as a vector of uints.
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
# File 'lib/geospatial/hilbert.rb', line 41 def self.unmap(transposed_index, bits) x = transposed_index.dup #var X = (uint[])transposedIndex.Clone(); n = x.length # n: Number of dimensions m = 1 << bits # Gray decode by H ^ (H/2) t = x[n-1] >> 1 # t = X[n - 1] >> 1; (n-1).downto(1) {|i| x[i] ^= x[i-1]} x[0] ^= t # Undo excess work q = 2 while q != m p = q - 1 i = n - 1 while i >= 0 if x[i] & q != 0 x[0] ^= p # invert else t = (x[0] ^ x[i]) & p; x[0] ^= t; x[i] ^= t; end i -= 1 end q <<= 1 end return x end |