Module: Geospatial::Hilbert

Defined in:
lib/geospatial/hilbert.rb,
lib/geospatial/hilbert/curve.rb

Defined Under Namespace

Classes: Curve

Class Method Summary collapse

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