Calcule o valor Hilbert de um ponto para uso em um Hilbert R-Tree?

Question

Tenho uma aplicação onde uma Hilbert R-Tree (wikipedia) (citeseer) parece ser uma estrutura de dados apropriada. Especificamente, ele requer consultas razoavelmente rápido espaciais mais de um conjunto de dados que irá experimentar um monte de atualizações.

No entanto, tanto quanto eu posso ver, nenhuma das descrições dos algoritmos para essa estrutura de dados, mesmo menção como realmente calcular o requisito Hilbert Valor ; que é a distância ao longo de uma Hilbert Curve ao ponto.

Assim, qualquer sugestões de como proceder para calcular isso?

Answer 1

questão Fun!

Eu fiz um pouco de googling, e a boa notícia é, eu encontrei uma implementação de Hilbert valor.

A potencialmente má notícia é que ele está em Haskell ...

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

Além disso, propõe uma distância Lebesgue métrica que você pode ser capaz de calcular com mais facilidade.

Answer 2

Abaixo está o meu código java adaptado a partir do código C no jornal "codificação e decodificação da ordem de Hilbert" por Xian Lu e Gunther Schrack, publicado em Software: prática e experiência Vol. 26 pp 1335-1346 (1996).

Espero que isso ajude. Melhorias bem-vindos!

Michael

/**
 * 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;
}

Answer 3

uzaygezen .

Answer 4

O código de código e java acima são muito bem para pontos de dados 2D. Mas para dimensões mais elevadas que você pode precisar de olhar para o papel de Jonathan Lawder: JKLawder . Cálculo de mapeamentos entre um e Valores n-dimensionais utilizando a curva Hilbert Space-enchimento.

Answer 5

Eu descobri uma maneira um pouco mais eficiente para intercalar bits. Ela pode ser encontrada no Stanford site Gráficos . Eu incluí uma versão que eu criei que pode intercalar dois de 32 bits inteiros em um 64 bits de comprimento.

public static long spreadBits32(int y) {
    long[] B = new long[] {
        0x5555555555555555L, 
        0x3333333333333333L,
        0x0f0f0f0f0f0f0f0fL,
        0x00ff00ff00ff00ffL,
        0x0000ffff0000ffffL,
        0x00000000ffffffffL
    };

    int[] S = new int[] { 1, 2, 4, 8, 16, 32 };
    long x = y;

    x = (x | (x << S[5])) & B[5];
    x = (x | (x << S[4])) & B[4];
    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];
    return x;
}

public static long interleave64(int x, int y) {
    return spreadBits32(x) | (spreadBits32(y) << 1);
}

Obviamente, o B e S variáveis ??locais devem ser constantes de classe, mas ele foi deixado dessa maneira para simplificar.

Answer 6

Michael,

obrigado por seu código Java! Eu testei-o e parece funcionar bem, mas eu notei que a função de intercalação pouco transborda a nível recursão 7 (pelo menos em meus testes, mas eu usei valores longos), porque o "n" -valor é calculada usando highestOneBit ( ) -função, que devolve o valor e não a posição da mais elevada, um bit; para que o loop faz desnecessariamente muitas interleavings.

Eu só mudou para o seguinte trecho, e depois disso ele trabalhou bem.

  int max = Math.max(odd, even);
  int n = 0;
  while (max > 0) {
    n++;
    max >>= 1;
  }

Answer 7

Se você precisa de um índice espacial com / rápido de exclusão inserção capacidades, ter um olhar para o PH-árvore. É parcialmente baseado em quadtrees mas mais rápido e mais eficiente do espaço. Internamente que utiliza um Z-curva que tem propriedades ligeiramente pior do que uma espaciais H-curva mas é muito mais fácil de calcular.

Papel: http://www.globis.ethz.ch/ script / publicação / download? docid = 699

Java implementação: http: // Globis .ethz.ch / files / 2014/11 / ph-tree-2014-11-10.zip

Outra opção é o X-árvore, que também está disponível aqui: https://code.google.com/p/xxl/

Answer 8

Sugestão:. Um bom simples estrutura de dados eficiente para consultas espaciais é uma árvore binária multidimensional

Em uma árvore binária tradicional, há uma "discriminante"; o valor que é usado para determinar se você tomar o ramo esquerdo ou ramo direito. Isto pode ser considerado o caso unidimensional.

Em uma árvore binária multidimensional, você tem várias discriminantes; níveis consecutivos usar diferentes discriminantes. Por exemplo, para dois dados espaciais tridimensionais, você poderia usar as coordenadas X e Y como discriminantes. níveis consecutivos usaria X, Y, X, Y ...

Para consultas espaciais (por exemplo encontrando todos os nós dentro de um retângulo) você faz uma busca em profundidade da árvore a partir da raiz, e você usar o discriminante em cada nível para evitar a procura para baixo ramos que não contêm nós na dado retângulo.

Isso permite que você potencialmente reduzir o espaço de busca na metade em cada nível, tornando-se muito eficiente para encontrar pequenas regiões em um conjunto de dados em massa. (Aliás, esta estrutura de dados também é útil para consultas parcial-jogo, ou seja, consultas que omitem um ou mais discriminantes. Você só procurar para baixo ambos os ramos em níveis com um discriminante omitido.)

Um papel bom em esta estrutura de dados: http://portal.acm.org /citation.cfm?id=361007 Este artigo tem boas diagramas e descrições de algoritmos: http://en.wikipedia.org/wiki/Kd -tree