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.

Parameters:

  • Point in N-space.

  • Depth of the Hilbert curve. If bits is one, this is the top-level Hilbert curve.

Returns:

  • The Hilbert distance (or index) as a transposed Hilbert index.



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.

Parameters:

  • The Hilbert index stored in transposed form.

  • Number of bits per coordinate.

Returns:

  • Coordinate vector.



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