IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++/CLI Discussion :

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


Sujet :

C++/CLI

  1. #1
    Membre du Club
    Inscrit en
    Février 2013
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : Février 2013
    Messages : 92
    Points : 49
    Points
    49
    Par défaut 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

  2. #2
    Modérateur
    Avatar de dinobogan
    Homme Profil pro
    ingénieur
    Inscrit en
    Juin 2007
    Messages
    4 073
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France

    Informations professionnelles :
    Activité : ingénieur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 4 073
    Points : 7 163
    Points
    7 163
    Par défaut
    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 ;-)
    N'oubliez pas de consulter les FAQ Java et les cours et tutoriels Java
    Que la force de la puissance soit avec le courage de ta sagesse.

  3. #3
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 317
    Points : 4 124
    Points
    4 124
    Par défaut Tableau ?
    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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  4. #4
    Membre du Club
    Inscrit en
    Février 2013
    Messages
    92
    Détails du profil
    Informations forums :
    Inscription : Février 2013
    Messages : 92
    Points : 49
    Points
    49
    Par défaut
    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).

    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.

    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.

  5. #5
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 317
    Points : 4 124
    Points
    4 124
    Par défaut Ordres de grandeur
    Bonjour,

    Prenons un exemple, pour un cube de 10 000 points de coté soit 1012 points 3D, avec un taux de remplissage de 10 % par axe il faudrait un tableau d'environ 230 é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 1013 recherches prendraient déjà 107 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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

Discussions similaires

  1. [Toutes versions] Comment exporter des données Excel vers une base Access
    Par BoGoss24 dans le forum Microsoft Office
    Réponses: 1
    Dernier message: 12/12/2019, 11h21
  2. [XL-2007] Comment enregistrer des données dynamique vers une base de données
    Par latizeva dans le forum Macros et VBA Excel
    Réponses: 1
    Dernier message: 20/11/2013, 00h03
  3. [Security] Mapper des infos LDAP vers un bean custom à l'aide de spring security
    Par thierryler dans le forum Spring
    Réponses: 3
    Dernier message: 26/07/2012, 11h03
  4. Réponses: 25
    Dernier message: 26/04/2011, 14h58
  5. Réponses: 16
    Dernier message: 21/03/2006, 00h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo