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