Comment mapper des coordonées 3d vers un index?

Bonjour à toutes et à tous,

J'ai un grand ensemble de points répartis dans un espace 3D (voire possiblement un espace en plus grandes dimensions) sous forme d'une lattice homogène comprise entre [-n, ..., n]^d
Je souhaite pouvoir indexer ces points dans un simple tableau en 1 dimension pour pouvoir les trouver sans parcourir mon tableau. Par exemple associer les coordonnées suivantes aux indexes:
{x1, y1, z1} donne idx1
{x2, y2, z2} donne idx2
{x3, y3, z3} donne idx3
etc.
Avec une précision: la lattice en 3d est centrée en {0,0,0} (donc {x1,y1,z1} = {0,0,0}).

Il me faut donc une fonction bijective de mapping qui, pour chaque point 3D, associe un index dans mon tableau. Ainsi quand je me trouve en {x1,y1,z1} je sais que dans mon tableau je peux aller chercher la valeur correspondante à l'indice 'idx1'.
Je dois réaliser cette opération un grand nombre de fois (de l'ordre de 10^13 fois au minimum, sans doute beaucoup plus).

Que me conseilleriez vous d'utiliser? je ne trouve pas de fonction de mapping.
Ma question porte vraiment pour la 3D mais s'il est possible de généraliser à 'd' dimensions avec d dans [1, n], ca m'intéresse aussi (mais c'est secondaire).

Merci
Edit: Je me suis trompé de catégorie, est-il possible de déplacer ce post dans la section C/C++ ? Merc

C'est "simplement" la généralisation du tableau 2D mapper en une dimension.
Mais il y a deux soucis majeurs :

1. il faut borner ton repère sur chaque axe.
2. ton tableau va être absolument gigantesque très vite et aura pleins de trous.

Sinon tu vas aligner les sous-tableaux de x1 consécutifs en partant du min x2 jusqu'au max x2 pour x3=min. Puis tu recommences pour x3=min+1.
Pour trouver l'index : x3 * (amplitude de x2) * (amplitude de x1) + x2 * (amplitude de x1) + x1

Tu étends à n dimensions.
Tu devrais plutôt t'orienter vers une autre structure, comme l'arbre B par exemple ou tout autre arbre équilibré. Ou encore une table de hashage, encore faut-il trouver la bonne fonction de hashage ;-)

Bonjour,

Comme déjà expliqué le tableau à trois dimensions est peu utilisable (saturation rapide de l'espace mémoire).

Outre les arbres, il est possible de stocker dans un tableau ou une liste, une structure x, y, z, index (ou peut être mieux pointeur) et de faire une recherche dichotomique sur x, y z. C'est assez rapide car en O(log n) ) et n'aura besoin que d'un tableau d'un taille proportionnée au nombre de points effectifs dans l'espace 3D.

Salutations

Merci pour vos retours éclairés!
Effectivement, rechercher c'est lent. J'essaye d'éviter cette solution, même avec des complexités de l'ordre de log(n), vu le nombre phénoménal d'appel à la fonction (j'ai une convergence très lente et en plus je suis obligé de simuler un certains nombre de fois = le pire des cas).

Citation:

---

Sinon tu vas aligner les sous-tableaux de x1 consécutifs en partant du min x2 jusqu'au max x2 pour x3=min. Puis tu recommences pour x3=min+1.
Pour trouver l'index : x3 * (amplitude de x2) * (amplitude de x1) + x2 * (amplitude de x1) + x1

---

Effectivement j'ai aussi pensé à l'indexation linéaire et j'ai testé mais je me retrouve avec des bornes tableaux vite immenses et effectivement beaucoup de trous dedans. Donc loin d'être pratique, mais par contre indexation instantanée.

Citation:

---

Ou encore une table de hashage, encore faut-il trouver la bonne fonction de hashage

---

Oui! C'est en fait ce que je recherche. Du coup, je m'oriente vers plusieurs options:

• mapper ces points dans une hypersphère et indéxer par un angle, mais ca me parait un peu compliqué (et la précision compte)
• la Courbe de Hilbert qui permet de mapper des hautes dimensions en plus basse dimensions, mais il faut que je creuse

Merci pour vos conseils je vais voir ce que je peux sortir de toutes ces propositions et si vous avez des idées additionnelles je suis preneur pour poovoir tester et regarder ce qui marche le mieux.

Bonjour,

Prenons un exemple, pour un cube de 10 000 points de coté soit 10¹² points 3D, avec un taux de remplissage de 10 % par axe il faudrait un tableau d'environ 2³⁰ éléments. Il faudra alors 30 accès pour chaque recherche, soit de l'ordre de la microseconde(avec anticipation c'est dire sans attente de données : je demande la donnée i, je traite la donnée i-a, je demande la donnée i+1, je traite la donnée i+1-a...).

Mais 10¹³ recherches prendraient déjà 10⁷ secondes c'est à dire plus de 10 ans !

En revanche, sur un tableau complet (assez irréaliste) la recherche serait 30 fois plus rapide se qui prendrait quand même 4 mois pour faire l'ensemble des recherches. Et en plus il y a des traitements !

A l'envers, en faisant des hypothèses de temps acceptable, de taux de remplissage de l'espace 3D, il est possible de calculer une taille maxi de l'espace 3D (vraisemblablement un cube de 1000 points de coté).

Salutations