Indexer des positions 3D en 1D

Bonjour à toutes et à tous,

J'ai un ensemble de n noeuds (n pouvant être grand) répartis sur une lattice homogène en 3 dimensions. Chaque noeud de la lattice est distant de son voisin d'une unité (distance=1).

Voici un exemple minimal pour n=27 noeudsPièce jointe 582644

Je cherche à faire correspondre les positions {x,y,z} de chacun de ces points à un index compris dans [0,n]. Cette correspondance doit être bijective et associer chaque tuple {x_i, y_i, z_i} à un index.
Cette question est dans le cadre d'une simulation numérique, et cette opération de correspondance est réalisée un nombre important de fois (de l'ordre de 10^10 au minimum), je cherche donc une correspondance peu couteuse en temps et sans recherche.

Je ne suis pas mathématicien, et en parcourant le net, je vois des topics sur les courbes paramétrées et les hypershères mais je ne comprends pas très bien comment approcher le problème d'un point de vue pratique.
Que me conseillerez vous de faire?

Merci à toutes et à tous d'avance pour vos suggestions.

Bonjour :coucou:

:D Il y a un multiplexage que tu utilises tous les jours sans même y penser : les nombres

598
5 sur l'axe des centaines
9 sur l'axe des dizaines
8 sur l'axe des unités.

Tu dis que c'est pour une utilisation informatique ?
Un autre exemple est la couleur RGBA. un octet par dimension. Et les couleurs sont donc sur 4 octets.

Le nombre entier qui résultera de ton multiplexage de valeurs binaires sera juste la concaténation des-dites valeurs binaires.
Facile à extraire, facile à modifier.

Tu as 27 points ? Sûrement 3*3*3. Donc si tu écris ton nombre en base 3, c'est gagné.
7₁₀ = 021₃ correspond à (x,y,z)=(-1,1,0)
0₁₀ = 000₃ correspond à (x,y,z)=(-1,-1,-1)
26₁₀ = 222₃ correspond à (x,y,z)=(1,1,1)

Citation:

---

Envoyé par Grasshoper

Bonjour à toutes et à tous,

J'ai un ensemble de n noeuds (n pouvant être grand) répartis sur une lattice homogène en 3 dimensions. Chaque noeud de la lattice est distant de son voisin d'une unité (distance=1).

Voici un exemple minimal pour n=27 noeudsPièce jointe 582644

---

Salut,
donc si je comprends bien, les coordonnées (x,y,z) de tes points vérifieront toujours -k ≤ x,y,z ≤ k avec n=(2k+1)³ ? k=1 pour ton exemple car n=27=(2×1+1)³.

Citation:

---

Envoyé par Grasshoper

Je cherche à faire correspondre les positions {x,y,z} de chacun de ces points à un index compris dans [0,n]. Cette correspondance doit être bijective et associer chaque tuple {x_i, y_i, z_i} à un index.
Cette question est dans le cadre d'une simulation numérique, et cette opération de correspondance est réalisée un nombre important de fois (de l'ordre de 10^10 au minimum), je cherche donc une correspondance peu couteuse en temps et sans recherche.

Je ne suis pas mathématicien, et en parcourant le net, je vois des topics sur les courbes paramétrées et les hypershères mais je ne comprends pas très bien comment approcher le problème d'un point de vue pratique.
Que me conseillerez vous de faire?

---

De faire simple dans ce cas : considère ton triplet comme une écriture en base 2k+1 d'un nombre à 3 chiffres → technique de l'odomètre ; tout ça à une translation près évidemment.
Si on commence par poser :

alors la fonction f : ℕ³→ℕ / (x',y',z') →x'+(2k+1)y'+(2k+1)²z' convient.
La fonction inverse consiste simplement à trouver la représentation d'un entier n en base 2k+1 et soustraire k à chaque élément du triplet.

Après c'est une solution simple qui ne prend pas du tout en compte d'autres contraintes comme une éventuelle recherche de localité dans les données accédées pour bénéficier d'un cache, par exemple. D'autres pistes de réflexions pourraient être plus efficaces …

edit: un peu grillé par Flo :mrgreen:

Je développe l'idée de Flodelarab : x varie entre 0 et X-1 , y varie entre 0 et Y-1 et z varie entre 0 et Z-1

Pour convertir (x,y,z) en un entier , ça donne n = x + y*X+ z*X*Y
Et à l'opposé, pour convertir n vers (x,y,z), ça donne :
x = mod(n,X)
y = mod((n-x)/X,Y)
z = (n-x-yX)/XY

Citation:

---

Envoyé par tbc92

Je développe l'idée de Flodelarab : x varie entre 0 et X-1 , y varie entre 0 et Y-1 et z varie entre 0 et Z-1

Pour convertir (x,y,z) en un entier , ça donne n = x + y*X+ z*X*Y
Et à l'opposé, pour convertir n vers (x,y,z), ça donne :
x = mod(n,X)
y = mod((n-x)/X,Y)
z = (n-x-yX)/XY

---

Exactement, c'est la technique de l'odomètre ou un système de numération à base variable. C'est simple et efficace.

Rebonjour et whoa! merci beaucoup pour toutes ces explications!
J'ai pris mon temps pour répondre afin de bien comprendre et bien lire ce qui était proposé, et ça marche très bien!
Ce qui est encore plus magique, c'est que c'est généralisable à d dimensions. J'ai réalisé un petit code Matlab pour tester:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

n = 2; %n valeurs in each dimension X = -n/2:n/2; %x [X,Y,Z] = ndgrid(X); data_points = [X(:), Y(:), Z(:)]; size_t = size(data_points,1);   kk=1; k = max(max(max(X))); %max dans chq dimensions for i=1:size_t   x = data_points(i,1); y = data_points(i,2); z = data_points(i,3);   idx = x + (2*k+1)*y + (2*k+1)^2*z;   p2(kk) = idx; kk = kk +1; end   %il faut rajouter un offset: p2 = p2 + max(p2);

---

Résultat:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

p2 =   Columns 1 through 10   0 1 2 3 4 5 6 7 8 9   Columns 11 through 20   10 11 12 13 14 15 16 17 18 19   Columns 21 through 27   20 21 22 23 24 25 26

---

J'ai du ajouter un offset car je voulais les valeurs dans [0, n-1].
Et c'est parfait!

Je marque comme résolu!

Une petite question supplémentaire sur ce sujet. Je cherche maintenant à faire l'étape inverse (cad récupérer les coordonnées d'un point à partir de son index) pour une grande lattice en 2D avec k=49 (soit N=99*99=9801 noeuds cette fois-ci). Comme vous l'avez tous souligné, et en particulier @WhiteCrown Il me faut trouver la représentation d'un entier 'n' en base 2k+1.
J'essaie donc avec un petit code matlab:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

k=49; x = 10; y = -1; base = 2*k+1; //calcul de l index n: n = x + base*y; //index obtenu //récupération des coordonnées à partir de n, soit x = 10 et y = -1 //pour x: quot = fix(n / base); //quotient x_recup = rem(n, base); //reste //pour y: quot2 = fix(quot / base); //quotient y_recup = rem(quot, base); //reste

---

Et donc pour x = 10 et y = -1 j'obtiens x_recup = -89 et y_recup = 0. J'ai une erreur que je ne comprends pas: je pars de ma base 2*k+1 et je récupère les modulos qui devraient me donner mes 'x' et 'y' attendus. Je pense donc avoir raté une étape quelque part, pouvez-vous m'éclairer?
Merci!

Citation:

---

Envoyé par Grasshoper

y = -1
(...)
pouvez-vous m'éclairer?

---

Si y=-1, c'est qu'il y a un décalage. Le changement de base de numération est une opération sur les nombres entiers positifs. Dans les derniers exemples de mon premier message, 0 devenait -1, 1 devenait 0, et 2 devenait 1.
Ton indice va de 0 à n-1. Donc tu peux transformer l'écriture de ton nombre entier positif en changeant la base de numération à 2k+1. Puis, il faut faire le décalage. 0 deviendra la plus petite valeur possible, 2k, la plus grande valeur, etc ...
Où est la soustraction ?

Je redis la même chose que Flodelarab, avec mes mots...

Les outils proposés marchent si les données en entrée sont des entiers, entre 0 et Xmax-1, entre 0 et Ymax-1, entre 0 et Zmax-1 etc etc
Si les données ne sont pas des nombres entiers, ou si tes nombres ne sont pas dans un intervalle simple, comme ci-dessus, il faut un pré-traitement en entrée (une table de conversion), pour travailler avec des entiers positifs, puis faire la gymnastique proposée.

Et quand tu fais l'opération inverse, bien entendu, il faut aussi appliquer cette table de conversion, mais à la fin.

La boite noire en question ne sait traiter que des entiers positifs.

Pourquoi utiliser des bases compliquées qui imposent des multiplications et des divisions très coûteuses en temps ? En utilisant une puissance de 2, des décalages et des 'and' suffisent. Et avec 2^8, il suffit d'adresser le bon octet.

Citation:

---

Envoyé par Nebulix

Pourquoi utiliser des bases compliquées qui imposent des multiplications et des divisions très coûteuses en temps ? En utilisant une puissance de 2, des décalages et des 'and' suffisent. Et avec 2^8, il suffit d'adresser le bon octet.

---

Pourquoi ? Peut-être parce que ça évite une débauche de mémoire, qu'elle conserve la localité ce qui est appréciable au niveau des caches de données … parce qu'on peut même accéder aux données séquentiellement …

L'objectif, c'est de proposer des solutions que le demandeur peut comprendre. Tout simplement. Ca porte un nom : la pédagogie.

Ici on a proposé une solution. C'était écrit noir sur blanc que les nombres (x,y,z) devaient être positifs , mais on n'avait pas mis l'accent suffisamment là dessus. Et le demandeur a fait un test. Ca plantait. Pourquoi ? Parce qu'un de ses nombres en entrée était négatif.

Et toi, tu proposes d'optimiser es temps de calcul, en remplaçant les multiplications/divisions par des multiplications/divisions par des puissances de 2 ???????

Bonjour à toutes à tous,

Je m'excuse d'avoir mis du temps à répondre.

Citation:

---

Le changement de base de numération est une opération sur les nombres entiers positifs

---

Effectivement, j'avais complètement raté ça. De fait, en ajoutant k pour la translation ça fonctionne super dans tous les sens maintenant!

Merci beaucoup!

Bonjour,

Il y a aussi l"entrelaçage" de bits qui permet de ne pas se limiter à une dimension donnée mais interdit tout calcul. Je l'utilise par exemple pour trier des couleurs car la distance moyenne entre couleur est assez faible ce qui permet de créer des chartes assez cohérentes avec n'importe quel ensemble de couleurs.
Color = G₇G₆G₅G₄G₃G₂G₁G₀, R₇R₆R₅R₄R₃R₂R₁R₀, B₇B₆B₅B₄B₃B₂B₁B₀
devient :
G₇R₇B₇G₆R₆B₆G₅R₅B₅G₄R₄B₄G₃R₃B₃G₂R₂B₂G₁R₁B₁G₀R₀B₀

Il y a des techniques de brassage qui permettent de faire cela assez rapidement.
Par ailleurs, il est possible d'écrire une condition de tri sans avoir besoin de faire le brassage de bits avec un masque initialisé à 0x808080 (ou un masque de composante initialisé à 0x80):

Code:

---

1 2 3 4 5

0x808080 -> mask tant que mask non nul mask & color1 - mask & color2 -> resultat si resultat non nul alors sortir de la boucle mask >> 1 -> mask

---

Salutations

J'ai l'impression qu'avec cette méthode, tu vas dire que les couleurs (127,127,127) et (128,127,127) sont très différentes, le bit le plus fort n'est pas le même, et donc ces 2 couleurs n'ont rien en commun.

Mais on est très très loin de la question initiale.

Bonjour Tbc,

Citation:

---

Envoyé par tbc92

J'ai l'impression qu'avec cette méthode, tu vas dire que les couleurs (127,127,127) et (128,127,127) sont très différentes, le bit le plus fort n'est pas le même, et donc ces 2 couleurs n'ont rien en commun.
Mais on est très très loin de la question initiale.

---

La question d'origine est bien de trouver une relation d'ordre à un espace multidimensionnel discret. L'entrelaçage de bits n'est qu'un moyen parmi d'autres.

Quelque soit l'indexation choisie elle présentera des irrégularités de distance (avec la concaténation GRB, la couleur 1, 0, 0 - vert très sombre - sera très proche de 0,255,255 - violet saturé). Ce qui est intéressant est la distance moyenne et sur ce plan, le brassage de bits est bien meilleur que la concaténation.
Petit exemple avec 2 bits par composante (plus les transitions sont courtes mieux c'est - les distances entre mini-cubes ne sont pas respectées pour éviter que cela soit illisible) :

Pièce jointe 585467

Salutations