Calculer la valeur de Hilbert d'un point à utiliser dans un arbre Hilbert R-Tree?
https://stackoverflow.com/questions/106237
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une application où un arbre Hilbert R-Tree (wikipedia) (citeseer) semble être une structure de données appropriée. Plus précisément, il nécessite des requêtes spatiales relativement rapides sur un ensemble de données qui subira de nombreuses mises à jour.
Cependant, autant que je sache, aucune des descriptions des algorithmes pour cette structure de données, même ne spécifie comment calculer réellement la valeur de Hilbert requise ; qui correspond à la courbe de Hilbert jusqu'au point.
Des suggestions sur la manière de calculer cela?
La solution
Question amusante!
J'ai fait quelques recherches sur Google et la bonne nouvelle est que j'ai trouvé une implémentation de Hilbert Value.
La mauvaise nouvelle est qu’elle est en Haskell ...
Il propose également une métrique de distance de Lebesgue que vous pourrez peut-être calculer plus facilement.
Autres conseils
Ci-dessous, mon code Java adapté du code C du document "Encodage et décodage de l'ordre de Hilbert". par Xian Lu et Gunther Schrack, publié dans Software: Practice and Experience Vol. 26 pages 1335-46 (1996).
J'espère que ça aide. Les améliorations sont les bienvenues!
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;
}
Voir uzaygezen .
Le code et le code Java ci-dessus conviennent aux points de données 2D. Mais pour les dimensions supérieures, vous devrez peut-être consulter l'article de Jonathan Lawder: JKLawder . Calcul des mappages entre les valeurs un et n-dimensionnelles à l'aide de la courbe de Hilbert remplissant l'espace.
J’ai trouvé un moyen légèrement plus efficace d’entrelacer les bits. Vous pouvez le trouver à l'adresse Site Web Stanford Graphics . J'ai inclus une version que j'ai créée qui peut entrelacer deux entiers de 32 bits en un seul de 64 bits.
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);
}
Évidemment, les variables locales B et S devraient être des constantes de classe, mais cela a été laissé ainsi pour des raisons de simplicité.
Michael,
merci pour votre code Java! Je l'ai testée et elle semble bien fonctionner, mais j'ai remarqué que la fonction d'entrelacement de bits débordait au niveau de récursivité 7 (du moins dans mes tests, mais j'avais utilisé des valeurs longues), car la valeur "n" est calculée à l'aide de mostOneBit. La fonction (), qui renvoie la valeur et non la position du bit le plus élevé; donc la boucle fait inutilement beaucoup d'entrelacement.
Je viens de le remplacer par l'extrait suivant, puis tout a bien fonctionné.
int max = Math.max(odd, even);
int n = 0;
while (max > 0) {
n++;
max >>= 1;
}
Si vous avez besoin d'un index spatial doté de fonctionnalités de suppression / insertion rapide, consultez l'arbre PH. Il repose en partie sur les quadtrees mais plus rapide et plus efficace en termes d'espace. En interne, il utilise une courbe en Z qui présente des propriétés spatiales légèrement inférieures à une courbe en H mais est beaucoup plus facile à calculer.
Papier: http://www.globis.ethz.ch/ script / publication / téléchargement? docid = 699
Implémentation Java: http: // globis .ethz.ch / dossiers / 2014/11 / ph-tree-2014-11-10.zip
Une autre option est l'arbre X, qui est également disponible ici: https://code.google.com/p/xxl/
Suggestion: une structure de données simple et efficace pour les requêtes spatiales est un arbre binaire multidimensionnel.
Dans un arbre binaire traditionnel, il existe un "discriminant"; la valeur utilisée pour déterminer si vous prenez la branche gauche ou la branche droite. Cela peut être considéré comme le cas unidimensionnel.
Dans un arbre binaire multidimensionnel, vous avez plusieurs discriminants; niveaux consécutifs utilisent différents discriminants. Par exemple, pour les données spatiales bidimensionnelles, vous pouvez utiliser les coordonnées X et Y comme discriminants. Les niveaux consécutifs utiliseraient X, Y, X, Y ...
Pour les requêtes spatiales (par exemple, recherche de tous les nœuds dans un rectangle), vous effectuez une recherche en profondeur dans l’arborescence à partir de la racine, puis vous utilisez le discriminant à chaque niveau pour éviter de rechercher dans les branches qui ne contiennent aucun nœud. rectangle donné.
Cela vous permet de réduire potentiellement l’espace de recherche de moitié à chaque niveau, ce qui le rend très efficace pour rechercher de petites régions dans un ensemble de données volumineux. (En outre, cette structure de données est également utile pour les requêtes de correspondance partielle, c’est-à-dire les requêtes qui omettent un ou plusieurs discriminants. Il vous suffit de rechercher les deux branches à des niveaux comportant un discriminant omis.)
Un bon article sur cette structure de données: http://portal.acm.org /citation.cfm?id=361007 Cet article contient de bons diagrammes et descriptions d'algorithmes: http://en.wikipedia.org/wiki/Kd -tree
