Discussion :

[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 noeuds

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.

[Flodelarab]

Bonjour

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)

[WhiteCrow]

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 noeuds

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)³.

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

[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

[WhiteCrow]

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.

[Grasshoper]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[Grasshoper]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[Flodelarab]

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 ?

[tbc92]

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.

[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.

[WhiteCrow]

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 …

[tbc92]

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 ???????

[Grasshoper]

Bonjour à toutes à tous,

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

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!

[Guesset]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

[Guesset]

Bonjour Tbc,

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) :

Salutations