comment choisir un algorithme ?

Version imprimable

28/12/2008, 10h44
polo77

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
28/12/2008, 11h15
PRomu@ld

Citation:

- 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.
28/12/2008, 11h47
polo77

Citation:

Envoyé par PRomu@ld

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) ?
29/12/2008, 09h29
PRomu@ld

Citation:

Les deux vont de pairs, non ?

Oui, mais on pourra toujours trouver des exceptions.

Citation:

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, ...
29/12/2008, 15h49
souviron34

Citation:

Envoyé par polo77

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..
:D