Вычислить гильбертово значение точки для использования в гильбертовом R-дереве?
-
01-07-2019 - |
Вопрос
У меня есть приложение, в котором R-дерево Гильберта (википедия) (цитируемый) казалось бы, это подходящая структура данных.В частности, для этого требуются достаточно быстрые пространственные запросы к набору данных, который будет постоянно обновляться.
Однако, насколько я могу видеть, ни одно из описаний алгоритмов для этой структуры данных даже упоминание как на самом деле рассчитать необходимое Значение Гильберта;которое равно расстоянию вдоль Кривая Гильберта ближе к делу.
Итак, есть какие-нибудь предложения о том, как это рассчитать?
Решение
Забавный вопрос!
Я немного погуглил, и хорошая новость в том, что я нашел реализацию значения Гильберта.
Потенциально плохая новость в том, что это в Haskell...
http://www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/
Он также предлагает метрику расстояния Лебега, которую вам, возможно, было бы проще вычислить.
Другие советы
Ниже приведен мой java-код, адаптированный из C-кода в статье "Кодирование и декодирование порядка Гильберта" Сианя Лу и Гюнтера Шрака, опубликованной в Software:Практика и опыт, Т.е.26 с. 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;
}
Видишь uzaygezen.
Приведенный выше код и java-код подходят для 2D-точек данных.Но для получения более высоких измерений вам, возможно, придется обратиться к статье Джонатана Лоудера: Дж.К.Лоудер.Вычисление отображений между одномерными и n-мерными значениями с использованием кривой заполнения Гильбертова пространства.
Я придумал немного более эффективный способ чередования битов.Его можно найти по адресу Веб-сайт 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 локальные переменные должны быть константами класса, но это было оставлено таким образом для простоты.
Майкл,
спасибо за ваш Java-код!Я протестировал его, и, кажется, он работает нормально, но я заметил, что функция чередования битов переполняется на уровне рекурсии 7 (по крайней мере, в моих тестах, но я использовал длинные значения), потому что значение "n" вычисляется с помощью функции highestOneBit(), которая возвращает значение, а не позицию старшего бита;таким образом, цикл выполняет излишне много чередований.
Я просто изменил его на следующий фрагмент, и после этого он работал нормально.
int max = Math.max(odd, even); int n = 0; while (max > 0) { n++; max >>= 1; }
Если вам нужен пространственный индекс с возможностью быстрого удаления / вставки, взгляните на PH-дерево.Он частично основан на деревьях квадрата, но быстрее и экономичнее в использовании пространства.Внутренне он использует 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-tree, который также доступен здесь:https://code.google.com/p/xxl/
Предложение:Хорошей простой эффективной структурой данных для пространственных запросов является многомерное двоичное дерево.
В традиционном двоичном дереве есть один "дискриминант".;значение, которое используется для определения того, выбираете ли вы левую ветвь или правую.Это можно рассматривать как одномерный случай.
В многомерном двоичном дереве у вас есть несколько дискриминантов;последовательные уровни используют разные дискриминанты.Например, для двумерных пространственных данных вы могли бы использовать координаты X и Y в качестве дискриминантов.Последовательные уровни будут использовать X, Y, X, Y...
Для пространственных запросов (например, для поиска всех узлов внутри прямоугольника) вы выполняете поиск в глубину дерева, начиная с корня, и используете дискриминант на каждом уровне, чтобы избежать поиска по ветвям, которые не содержат узлов в данном прямоугольнике.
Это позволяет вам потенциально сократить пространство поиска вдвое на каждом уровне, что делает его очень эффективным для поиска небольших областей в огромном наборе данных.(Кстати, эта структура данных также полезна для запросов с частичным совпадением, т.е.запросы, в которых опущен один или несколько дискриминантов.Вы просто выполняете поиск в обеих ветвях на уровнях с опущенным дискриминантом.)
Хорошая статья об этой структуре данных: http://portal.acm.org/citation.cfm?id=361007 В этой статье есть хорошие диаграммы и описания алгоритмов: http://en.wikipedia.org/wiki/Kd-tree