计算用于希尔伯特R树的点的希尔伯特值？

我有一个应用程序,其中Hilbert R-Tree (维基百科) (citeseer)似乎是一个合适的数据结构.具体而言,它需要对将经历大量更新的数据集进行合理快速的空间查询.

但是,据我所知,这个数据结构的算法描述都没有提到如何实际计算必要的希尔伯特值 ; 这是希尔伯特曲线到该点的距离.

那么有关如何计算这个的任何建议？

有趣的问题!

我做了一些谷歌搜索,好消息是,我找到了希尔伯特价值的实现.

潜在的坏消息是,它在Haskell ......

http://www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/

它还提出了一个您可能更容易计算的Lebesgue距离度量.

下面是我的java代码,改编自Xian Lu和Gunther Schrack撰写的"编码和解码希尔伯特顺序"中的C代码,发表于Software:Practice and Experience Vol.26 pp 1335-46(1996).

希望这可以帮助.欢迎改进!

迈克尔

/**
 * Find the Hilbert order (=vertex index) for the given grid cell 
 * coordinates.
 * @param x cell column (from 0)
 * @param y cell row (from 0)
 * @param r resolution of Hilbert curve (grid will have Math.pow(2,r) 
 * rows and cols)
 * @return Hilbert order 
 */
public static int encode(int x, int y, int r) {

    int mask = (1 << r) - 1;
    int hodd = 0;
    int heven = x ^ y;
    int notx = ~x & mask;
    int noty = ~y & mask;
    int temp = notx ^ y;

    int v0 = 0, v1 = 0;
    for (int k = 1; k < r; k++) {
        v1 = ((v1 & heven) | ((v0 ^ noty) & temp)) >> 1;
        v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
    }
    hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));

    return interleaveBits(hodd, heven);
}

/**
 * Interleave the bits from two input integer values
 * @param odd integer holding bit values for odd bit positions
 * @param even integer holding bit values for even bit positions
 * @return the integer that results from interleaving the input bits
 *
 * @todo: I'm sure there's a more elegant way of doing this !
 */
private static int interleaveBits(int odd, int even) {
    int val = 0;
    // Replaced this line with the improved code provided by Tuska
    // int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even));
    int max = Math.max(odd, even);
    int n = 0;
    while (max > 0) {
        n++;
        max >>= 1;
    }

    for (int i = 0; i < n; i++) {
        int bitMask = 1 << i;
        int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0;
        int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0;
        val += a + b;
    }

    return val;
}