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)

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

[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