Si j'ai un jeu de données, où les clés sont des points en 3D, représentés par 3 entiers 64 bits signés. Et je souhaite utiliser un magasin de valeur de clé (trié) pour les stocker, où les touches ne sont que de l'ensemble d'octet (mais je peux spécifier un comparateur). Je pense que je peux transformer tous ces points en une matrice d'octet à l'aide de l'entrelacement bit, comme cela est fait avec Z / Morton Command comme dans Comment calculer un numéro de morton 3D
En plus de récupérer des points individuels, qui peuvent être effectués plus simplement sans commander à morton, je souhaite faire une recherche de portée, où je recherche dans une boîte alignée sur les axes. Je définirai A et B comme étant respectivement les coins de la boîte où toutes les coordonnées sont les plus bas et le coin opposé où toutes les coordonnées sont les plus élevées.
Maintenant, mes questions sont:
Pour tout point C, qui est logiquement entre, A et B, le nombre de morton de C soit également entre le nombre de Morton d'A et B? (N'est-ce pas le point d'ordre de Morton?)
Si 1 est non, peut-on et b être "arrondi" aux valeurs qui garantissent que c sera inclus?
supposant que 1 ou 2 est possible, la recherche renvoie-t-elle également des points à l'extérieur de cette boîte, que je dois "post-filtre"? Quelle est la taille de cette "erreur d'erreur" (dépend-elle de la taille ou de la position, de la recherche)?
Le fait que les entiers soient signés causent des problèmes? Et si oui, y a-t-il un travail-autour?
Pour récapituler, à l'aide de NUMÉROS MORTON n'est qu'une solution possible au problème réel: la recherche de manière efficace dans l'espace entier 3D, lorsque les points 3D doivent être mappés sur une valeur unidimensionnelle? Je veux obtenir tous les points entre A et B, en effectuant une seule gamme Sélectionnez dans la DB, à l'aide d'une touche MIN et d'une clé max, et idéalement, d'obtenir aussi peu de points à l'extérieur de la boîte. aussi possible.
3 Réponses :
On dirait que je dois répondre à ma question moi-même. Et la réponse se rapportera à la courbe d'ordre z, qui est ce que je réellement demandé. Ceci est aussi loin que je l'obtiens:
Il semble que je dis est pas clair, donc je vais faire un peu d'art ASCII ... p>
Un ordre Z de base courbe (Morton commande) en 2D va comme ceci (chemin d'accès est A, B, C, D): p>
SELECT key,data FROM table WHERE (key >= Hilbert(XXX(box))) AND (key <= Hilbert(YYY(box)))
IIUC Si A et B sont des coins de la zone de recherche, vous prenez le plus long préfixe commun de Morton (A) et Morton (B) pour trouver la plus grande "zone Z" qui contient la zone de recherche et répéter cet algorithme à travers la dichotomie, c'est que correct?
@Amirouche il y a 3 ans, et je suis depuis longtemps abandonné ce projet (pour des raisons non liées à cette question), sans parler de l'utilisateur Morton (ou Hilbert) à nouveau, alors j'ai tout oublié, et je ne peux pas (compétent) répondre à votre question. Pardon.
La source de révélation est vision-tools.com/h-tropf/multidimensionalrangequery.pdf < / a> via WP; Merci!
4) Oui, le panneau provoquera un problème, mais il est trivial de résoudre.
Just Xor le bit de signe de x, y et z avec 1 avant de créer votre numéro de morton.
Pourquoi cela fonctionne (en utilisant 1 dimension signé des octets à la place):
-1 en binaire est 11111111
0 en binaire est 00000000
1 en binaire est 00000001
La commande que vous voulez est -1, 0, 1, mais l'ordre binaire actuel est 0, 1, -1.
-1 xor 10000000 = 01111111
0 xor 10000000 = 10000000
1 xor 10000000 = 10000001
maintenant votre ordre binaire est correct
C'était la dernière partie du puzzle, si je tiens à l'ordre de Morton.
D'ACCORD. Je pense que ma réponse et ma réponse résolument tous les points de ma question. Et je détesterais avoir une prime aller à perdre, je peux donc vous le donner. En supposant que vous avez compris ma question et ma réponse, j'apprécierais que si vous pouviez au moins me dire si cela semble juste, car je ne suis pas totalement sûr et que je n'ai reçu aucun retour sur ma propre réponse, pas même un + / - voter.
@Sebastien DIOT - Je pense que 1) est "non" qui fait référence à l'article Wikipedia, l'exemple 2D donné montre que même dans une plage, vous aurez toujours besoin de caresser les faux positifs ou de calculer les numéros de morton intermédiaires et de la requête de plusieurs gammes. en.wikipedia.org/wiki/morton_number_%28Number_theory%29
Merci. Je vais vérifier cela à nouveau.
D'ACCORD. J'ai vérifié. Je pense que ma théorie détient: Si vous regardez la table avec la représentation binaire et choisissez deux points (x, y) au hasard, disons, (2,5) et (6,3). Ensuite, la boîte est: (2,3), (2,5), (6,5), (6,3) (commande n'est pas importante). Maintenant, vous prenez le point «le plus bas», (2,3) comme début et le «plus élevé», (6,5) en fin de compte. Si vous suivez la courbe de (2,3) à (6,5), il couvrira tous les points de la boîte (avec beaucoup d'autres, mais cela est résolu par post-filtrage).
Il n'y a pas grand chose que vous pouvez vous attendre à essayer de réduire les 3 dimensions à 1 dimension. Ce que vous pourriez essayer cependant: trouvez l'axe majeur (c'est-à-dire une ligne qui ajuste à travers vos points), puis projetez les points sur la ligne. Cela vous donne une valeur d'un dimension demandée pour chaque point. Lorsque vous projetez les coins des cases sur la ligne et prenez l'intervalle de ces valeurs, vous obtenez la plage de recherche.
Ou 5: vous pouvez prendre deux numéros de morton
(a, b, c) et(d, e, f) et les ajouter de manière intelligente et rapide (donc pas de désentrelacement ni d'entrelacement et d'entrelacement ) Pour obtenir(A + D, B + E, C + F) , vous pouvez ainsi analyser cette case dans la commande normale. Êtes-vous intéressé par cette technique aussi?@HAROLD Je ne comprends pas comment l'ajout aide, mais si c'est une solution à la recherche de la plage, je serais intéressé.
Eh bien, peut-être que je ne comprends pas votre problème, mais vous voulez chercher dans une boîte, non? Comme dans, visitez tous les éléments de cette boîte et effectuez probablement une sorte de test sur l'élément? Ce que j'avais à l'esprit était la même idée que trois boucles imbriquées sur
x ,y etz mais évite de convertir toutes ces coordonnées en Morton Nombres en incrémentant directement les champs de la coordonnée Morton.Ok, je pense que je vais avoir votre idée, en partie. Mais je ne suis pas sûr que cela s'applique. Je veux obtenir tous les points entre A et B, en effectuant une seule gamme Sélectionnez dans la DB, à l'aide d'une touche MIN et d'une clé max. Je pense que votre solution, en utilisant une boucle, impliquerait de nombreux appels de DB, si je comprends bien correctement.
Oh, oui, je pensais que nous parlions simplement de quelque tableau dans la RAM ici, ce qui complique des questions
Demander toute la gamme ne saurait rien sauter, mais cela vous donnerait une charge complète de données inutiles. Vraiment beaucoup.