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

Algorithmes et structures de données Discussion :

comment choisir un algorithme ?


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    8
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 8
    Points : 5
    Points
    5
    Par défaut comment choisir un algorithme ?
    Bonjour à tous,
    (je ne suis pas un ''matheu'')
    bien qu'ayant lu la F.A.Q. sur les algorithmes, il est difficile de choisir un algo.
    existe t-il des livres ou tutoriels traitant le choix d'algorithmes ?
    prenons mon cas (par exemple):
    - Je souhaite trouver un algo qui me permette de stocker et de sélectionner le plus rapidement possible des donnés vectoriels (pour une application 2D/3D)?
    plusieurs questions en découlent :
    comment écrire mes donnés (en mémoire et physiquement) et pourquoi ?
    comment sélectionner et stocker mes donnés ?
    comment sérialiser celles-ci ?
    pour la ''sérialisation'' j'avais pensé au xml (''gzipé''). mais connaissant un peu ce monde (le format dxf ou svg (pour la 2D) s'agit-il d'un bon choix ? oui/non pourquoi ?).
    Au même titre que la modélisation d'une application est importante dans un projet pouvons nous dire que le choix d'algo. en découle ou l'inverse.
    Ayant de bonnes bases en LISP est-ce que ce langage est représentatif (sur l'efficacité du choix de l'algo mis a part?
    J'espère ne pas avoir été trop confus, merci

  2. #2
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    - Je souhaite trouver un algo qui me permette de stocker et de sélectionner le plus rapidement possible des donnés vectoriels (pour une application 2D/3D)?
    En fait, il faut que tu nous décrives quel est le point le plus important pour toi : la rapidité de récupération ou la quantité de stockage ? De plus comment souhaites-tu récupérer les données (quels sont tes critères de sélection).

    Intuitivement, je pense qu'il faut que tu utilises une structure accélératrice QuadTree,BSP,... Mais n'en sachant pas plus sur ce que tu veux faire exactement, ça ne vaut pas le coup de s'étendre.

  3. #3
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    8
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 8
    Points : 5
    Points
    5
    Par défaut
    Citation Envoyé par PRomu@ld Voir le message
    En fait, il faut que tu nous décrives quel est le point le plus important pour toi : la rapidité de récupération ou la quantité de stockage ? De plus comment souhaites-tu récupérer les données (quels sont tes critères de sélection).

    Intuitivement, je pense qu'il faut que tu utilises une structure accélératrice QuadTree,BSP,... Mais n'en sachant pas plus sur ce que tu veux faire exactement, ça ne vaut pas le coup de s'étendre.
    Les deux vont de pairs, non ?
    souhaitant réaliser un logiciel-métier 2D/3D je me demandais comment la société (AutoCAD faisait pour rendre aussi efficace sa sélection d'objets !!)
    le plus important est la possibilité de sélectionner les objets dans un espace de coordonnées cartésienne, pouvoir récupérer par ''survol" ou par sélection (rectangulaire/survol/lasso) un ou plusieurs objets.
    Lorsque-tu dis QuadTree,BSP tu veux parler de boite ''englobantes'' ? où chacune des boites est représentées par une matrice et son vecteur (matrice4x4) ?

  4. #4
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    Les deux vont de pairs, non ?
    Oui, mais on pourra toujours trouver des exceptions.

    Lorsque-tu dis QuadTree,BSP tu veux parler de boite ''englobantes'' ? où chacune des boites est représentées par une matrice et son vecteur (matrice4x4) ?
    Pas tout à fait.

    En fait, suivant la structure de données utilisé, la méthode un un peu différente mais l'esprit reste le même : réaliser une partition de l'espace.

    L'idée d'un QuadTree (ou plutôt d'un Octree dans le cas 3D), c'est de subdiviser l'espace en 4 (en 8 pour la 3D) de façon régulière. Tu arrêtes de subdiviser suivant plusieurs critères (l'espace restant à découper est trop faible, tu as trop subdivisé, il ne reste presque plus que X objets dans l'espace).

    Dans un octree, tu as besoin (au minimum) de la boîte englobante de la scène, puis de pointeurs vers les fils (ie: les noeuds). Un noeud contient (au minimum) des pointeurs vers les fils et des pointeurs vers les objets.

    Dans un BSP, c'est un peu différent, l'idée est de partitionner l'espace en 2 par des plans de découpe. Tes plans de découpe peuvent être alignés aux axes (c'est alors un Kd-Tree). Ici, il faut que tu stockes dans chacun des noeuds, l'axe de découpe (vecteur dans le cas d'un BSP, un entier dans le cas d'un Kd-Tree), la position sur l'axe de découpe (un réel), un pointeur vers le fils gauche, un pointeur vers le fils droit et si tu es sur une feuille un/des pointeur(s) sur le(s) objet(s).

    Il y a un tas d'autres structures de données. Le tout est de choisir celle qui te convient le mieux.

    Il faut aussi savoir que dans les logiciels comme autocad,3dsmax, ... Il y a bien souvent une structure qui gère la topologie des objets (relations d'adjacences entre les objets, faces, points). Ca permet de rapatrier rapidement tous les objets proches d'un point, arête, face, ...

  5. #5
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par polo77 Voir le message
    Les deux vont de pairs, non ?
    souhaitant réaliser un logiciel-métier 2D/3D je me demandais comment la société (AutoCAD faisait pour rendre aussi efficace sa sélection d'objets !!)
    le plus important est la possibilité de sélectionner les objets dans un espace de coordonnées cartésienne, pouvoir récupérer par ''survol" ou par sélection (rectangulaire/survol/lasso) un ou plusieurs objets.
    Lorsque-tu dis QuadTree,BSP tu veux parler de boite ''englobantes'' ? où chacune des boites est représentées par une matrice et son vecteur (matrice4x4) ?
    Tout dépend de ce que dois faire ton logiciel métier et des contraintes...

    AutoCAD n'est pas forcément un modèle de rapidité d'affichage...

    Par contre c'est un bon modèle de structuration.. Mais utilisant pas mal de mémoire..

    Tout dépend du volume (nombre) de tes vecteurs, de leurs relations, du fait de savoir si leurs coordonnées sont entières, réelles, si il y aura beaucoup de calculs d'intersections à faire, si ils appartiennent à des surfaces, si ils se modifient au cours du temps, dans quels types de calculs ils seront utilisés, etc etc...

    Une bonne analyse de départ te (et nous par la même occasion) permettra d'identifier correctement les propriétés essentielles. A partir de là, on pourra réfléchir à une une structuration de fabrication/gestion optimisée de manière structurelle/programmatique..
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

Discussions similaires

  1. Réponses: 7
    Dernier message: 15/08/2005, 19h13
  2. [Lumières] Comment choisir les lumières à activer ?
    Par bigquick dans le forum OpenGL
    Réponses: 3
    Dernier message: 30/10/2004, 02h58
  3. Association : comment choisir le sens ?
    Par 1cado dans le forum Diagrammes de Classes
    Réponses: 2
    Dernier message: 27/09/2004, 00h12
  4. [JSP][Tomcat] COmment choisir la place des fichiers .class?
    Par mathieu dans le forum Tomcat et TomEE
    Réponses: 16
    Dernier message: 03/03/2004, 10h24
  5. Comment choisir une langue differente de la locale?
    Par julian_ross dans le forum Eclipse Java
    Réponses: 1
    Dernier message: 01/03/2004, 19h08

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