module Geospatial::Hilbert
Public Class Methods
map(hilbert_axes, bits)
click to toggle source
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. @param hilbert_index Point
in N-space. @param bits Depth of the Hilbert
curve. If bits is one, this is the top-level Hilbert
curve. @return The Hilbert
distance (or index) as a transposed Hilbert
index.
# 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)
click to toggle source
Convert the Hilbert
index into an N-dimensional point expressed as a vector of uints. @param transposed_index The Hilbert
index stored in transposed form. @param bits Number of bits per coordinate. @return Coordinate vector.
# 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