Рассчитать значение Гильберта точки для использования в R-дереве Гильберта?

Question

У меня есть приложение, в котором R-дерево Гильберта (википедия) (цитирующий) представляется подходящей структурой данных. В частности, требуются достаточно быстрые пространственные запросы к набору данных, которые будут подвергаться множеству обновлений.

Однако, насколько я вижу, ни одно из описаний алгоритмов для этой структуры данных даже не упоминает , как на самом деле вычислить требуемый Значение Гильберта ; это расстояние по кривой Гильберта до точки.

Итак, есть ли какие-либо предложения о том, как рассчитать это?

Answer 1

Веселый вопрос!

Я немного погуглил, и хорошие новости в том, что я нашел реализацию Hilbert Value.

Потенциально плохие новости в Хаскеле ...

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

Он также предлагает метрику расстояния Лебега, которую вы могли бы вычислить более легко.

Answer 2

Ниже приведен мой java-код, адаптированный из кода C в статье «Кодирование и декодирование порядка Гильберта» Сианя Лу и Гюнтера Шрака, опубликованной в Software: Practice and Experience Vol. 26 с. 1335-46 (1996).

Надеюсь, это поможет. Улучшения приветствуются!

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

Код и код Java, приведенные выше, подходят для точек 2D данных. Но для более высоких измерений вам, возможно, придется взглянуть на статью Джонатана Лоудера: J.K.Lawder. Расчет отображений между одномерными и n-мерными значениями с использованием кривой заполнения пространства Гильберта.

Answer 4

См. Узайгезен .

Answer 5

Я нашел немного более эффективный способ чередования битов. Его можно найти на сайте Stanford Graphics . Я включил созданную мной версию, которая может чередовать два 32-битных целых числа в одно 64-битное.

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);
}

Очевидно, что локальные переменные B и S должны быть константами класса, но для простоты они были оставлены.

Answer 6

Michael

спасибо за ваш код Java! Я проверил это, и оно, кажется, работает нормально, но я заметил, что функция чередования битов переполняется на уровне рекурсии 7 (по крайней мере, в моих тестах, но я использовал длинные значения), потому что значение "n" вычисляется с использованием наивысшего значения () ) -функция, которая возвращает значение, а не позицию старшего бита; поэтому цикл делает излишне много чередований.

Я просто изменил его на следующий фрагмент, и после этого он работал нормально.

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

Answer 7

Если вам нужен пространственный индекс с возможностью быстрого удаления / вставки, взгляните на PH-дерево. Это частично основано на quadtree, но быстрее и более экономно. Внутренне он использует Z-кривую, которая имеет несколько худшие пространственные свойства, чем H-кривая, но ее намного легче вычислить.

Бумага: http://www.globis.ethz.ch/script/publication/download?docid=699

Реализация Java: http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip

Другим вариантом является X-дерево, которое также доступно здесь: https://code.google.com/p/xxl/

Answer 8

Предложение. Хорошей простой и эффективной структурой данных для пространственных запросов является многомерное двоичное дерево.

В традиционном бинарном дереве есть один «дискриминант»; значение, которое используется для определения того, выбираете ли вы левую или правую ветку Это можно считать одномерным случаем.

В многомерном бинарном дереве у вас есть несколько дискриминантов; последовательные уровни используют разные дискриминанты. Например, для двумерных пространственных данных вы можете использовать координаты X и Y в качестве дискриминантов. Последовательные уровни будут использовать X, Y, X, Y ...

Для пространственных запросов (например, для нахождения всех узлов в прямоугольнике) вы выполняете поиск в глубину дерева, начинающегося с корня, и используете дискриминант на каждом уровне, чтобы избежать поиска вниз по ветвям, которые не содержат узлов в данный прямоугольник.

Это позволяет вам потенциально сократить пространство поиска пополам на каждом уровне, что делает его очень эффективным для поиска небольших областей в массивном наборе данных. (Кстати, эта структура данных также полезна для запросов с частичным совпадением, то есть запросов, в которых пропущен один или несколько дискриминантов. Вы просто просматриваете обе ветви на уровнях с пропущенным дискриминантом.)

Хорошая статья об этой структуре данных: http://portal.acm.org/citation.cfm?id=361007 В этой статье есть хорошие схемы и описания алгоритмов: http://en.wikipedia.org/wiki/Kd-tree