design : décorreller un algo de parcours, de la structure parcourue. hashmaps ?

Le
meow
Bonjour,

En préliminaires, description du problème :
J'ai une classe ObjetVolumique qui me permet de représenter des
objets comme un ensemble de points, d'arretes, de triangles et de
tétraedres avec des relations d'incidences qui vont bien (c.à.d que
j'ai un moyen savoir quel triangle est une face de quel tetraedre, que
tetraedre est le voisin de qui et par quelle face, quels sont les
sommets de tel tétraedre, etc).
Or pour certaines observations je suis amené à m'intéresser
essentiellement au "bord" de cet objet, soit donc à considérer une
classe ObjetSurfacique dont j'instancierai un objet a partir d'un
instance d'ObjetVolumique. L'algo de construction d'un objet
surfacique consiste essentiellement en une promenade dans les
tétraedres de mon objet volumique et demande à ce que je puisse
laisser des traces du parcours (suis-je déjà passé dans ce tétraedr=
e ?
Ais-je déja créé l'arrete de mon objet surfacique correspondant a
cette arrete de l'objet volumique ? ).

Ma friche :
Jusqu'à présent, j'ai modifié les classes interne d'ObjetVolumique
(ObjetVolumique::tétraedres et Cie) afin qu'elles hébergent les
"échafaudages" de l'algo de construction d'ObjetSurfacique Ce qui
est laid à plusieurs égards, ne serait-ce que parce qu'ObjetVolumique
n'a en définitive rien à voir avec l'algorithme en question et ne
devrait donc pas se trouver correllé avec lui

1.) Ma question :
Je cherche un moyen d'opérer cette décorrellation !

2.) Ma seconde question : Une réponse possible
On a attiré mon attention sur les hash_map, et si je comprends bien
l'utilisation de la chose : au lieu de stocker mes infos de
construction ConstructionInfo dans les ObjetVolumique::tetraedre, je
les stockerai dans un
hash_map<ObjetVolumique::tetraedre,ConstructionInfo>.
Si cela vous semble une bonne méthode j'aurai deux autres questions :

a.) visiblement tetraedre n'est pas automatiquement géré pour la
fonction de hashage Du coups il faudrait que j'en écrive une Je
pensais utiliser l'adresse mémoire du tétraèdre pour me ramener à u=
ne
fonction de hachage qui, elle, serait déjà défine Mais bon
tretraedre* n'est à priori pas plus géré que tétraèdre, il faudra=
it
donc que je fasses une conversion vers un "type intégral"(?) géré
C'est quoi un type intégral ? Comment je peux faire ça ? Une autre
idée ?

b.) design encore : pour l'implémentation de mon algo j'envisage une
classe VolumiqueToSurfacique qui contiendrait un hash map comme décrit
ci dessus ça parrait correct ?
A la limite, il peut etre meme que j'englobe ce hash-map dans une
structure qui me donne une interface plus spécifique à mon algo
genre un TetraInfos qui aggregerait un hash map et fournirait des
fonctions du type isTetraSeen(tetraedre), getTetraEdge(tetraedre)
etc
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Michael DOUBEZ
Le #308929
Bonjour,

En préliminaires, description du problème :
J'ai une classe ObjetVolumique qui me permet de représenter des
objets comme un ensemble de points, d'arretes, de triangles et de
tétraedres avec des relations d'incidences qui vont bien (c.à.d que
j'ai un moyen savoir quel triangle est une face de quel tetraedre, que
tetraedre est le voisin de qui et par quelle face, quels sont les
sommets de tel tétraedre, etc...).
Or pour certaines observations je suis amené à m'intéresser
essentiellement au "bord" de cet objet, soit donc à considérer une
classe ObjetSurfacique dont j'instancierai un objet a partir d'un
instance d'ObjetVolumique. L'algo de construction d'un objet
surfacique consiste essentiellement en une promenade dans les
tétraedres de mon objet volumique et demande à ce que je puisse
laisser des traces du parcours (suis-je déjà passé dans ce tétraedre ?
Ais-je déja créé l'arrete de mon objet surfacique correspondant a
cette arrete de l'objet volumique ? ).


D'après ce que je vois ta classe ObjetVolumique a deux responsabilité:
1 stocker les tétraedres qui la compose
2 donner l'organisation geograpghique des éléments du volume
Et maintenant tu te retrouve avec un algo qui a besoin de voir ta classe
en tant que conteneur mais ne fournit pas l'interface pour.

Tes choix sont:
1. Séparer les deux concepts: je ne sais pas si ça fait sens dans ton cas.
2. Ajouter les fonctionalités de container à ta classe: par exemple
ajouter des itérateurs mais c'est justement ton problème
3. Ajouter des informations de l'algo dans tes classes: ce que tu as
essayé mais ça recommencera le jour ou tu aura besoin d'un autre algo
4. Externaliser l'information: ce que tu as voulu faire avec ta table de
hashage

Je te conseillerais la solution 1 ou la 2.
Je ne connais pas le domaine ni ton impléménetation donc c'est dur de te
consiller mais par exemple:
- La 1 peut se faire simplement en ajoutant un set<> dans un objet
interface (racine) avec les fonctions d'ajout qui vont bien et te donne
accès à ton volume.
- La 2 peut se faire en trouvant une heuristique de passage dans tes
tétraedres (peut être en les marquants ou en les numérotant).


Ma friche :
Jusqu'à présent, j'ai modifié les classes interne d'ObjetVolumique
(ObjetVolumique::tétraedres et Cie) afin qu'elles hébergent les
"échafaudages" de l'algo de construction d'ObjetSurfacique... Ce qui
est laid à plusieurs égards, ne serait-ce que parce qu'ObjetVolumique
n'a en définitive rien à voir avec l'algorithme en question et ne
devrait donc pas se trouver correllé avec lui...

1.) Ma question :
Je cherche un moyen d'opérer cette décorrellation !


Ca ressemble à un cas de visitor mais il te faut pour ça itérer sur tout
tes éléments.

2.) Ma seconde question : Une réponse possible
On a attiré mon attention sur les hash_map, et si je comprends bien
l'utilisation de la chose : au lieu de stocker mes infos de
construction ConstructionInfo dans les ObjetVolumique::tetraedre, je
les stockerai dans un
hash_map<ObjetVolumique::tetraedre,ConstructionInfo>.
Si cela vous semble une bonne méthode j'aurai deux autres questions :


Si tu doit stocker une information par élément surfacique ça fait sens.


a.) visiblement tetraedre n'est pas automatiquement géré pour la
fonction de hashage... Du coups il faudrait que j'en écrive une... Je
pensais utiliser l'adresse mémoire du tétraèdre pour me ramener à une
fonction de hachage qui, elle, serait déjà défine... Mais bon...
tretraedre* n'est à priori pas plus géré que tétraèdre, il faudrait
donc que je fasses une conversion vers un "type intégral"(?) géré...
C'est quoi un type intégral ? Comment je peux faire ça ? Une autre
idée ?


Tu peux utiliser une map mais la conversion d'un pointer vers un long
est garantie (ou est ce long long ?) en tous cas ça marche.


b.) design encore : pour l'implémentation de mon algo j'envisage une
classe VolumiqueToSurfacique qui contiendrait un hash map comme décrit
ci dessus... ça parrait correct ?
A la limite, il peut etre meme que j'englobe ce hash-map dans une
structure qui me donne une interface plus spécifique à mon algo...
genre un TetraInfos qui aggregerait un hash map et fournirait des
fonctions du type isTetraSeen(tetraedre), getTetraEdge(tetraedre)
etc...


Ta structure peut être générique et fournir le moyen de la remplir en
parcourant tous les éléments d'un ObjetVolumique avec un prédicat et un
inserter.

Ca dépend de tes besoins et de l'utilisation classique de ta structure.
Mais à mon avis ça se joue entre les solutions de type 1 et 2
mentionnées ci-dessu.

Michael

Michael DOUBEZ
Le #308904
[snip]
b.) design encore : pour l'implémentation de mon algo j'envisage une
classe VolumiqueToSurfacique qui contiendrait un hash map comme décrit
ci dessus... ça parrait correct ?
A la limite, il peut etre meme que j'englobe ce hash-map dans une
structure qui me donne une interface plus spécifique à mon algo...
genre un TetraInfos qui aggregerait un hash map et fournirait des
fonctions du type isTetraSeen(tetraedre), getTetraEdge(tetraedre)
etc...


Ta structure peut être générique et fournir le moyen de la remplir en
parcourant tous les éléments d'un ObjetVolumique avec un prédicat et un
inserter.

Ca dépend de tes besoins et de l'utilisation classique de ta structure.
Mais à mon avis ça se joue entre les solutions de type 1 et 2
mentionnées ci-dessus.


Après réflexion, pour une solution rapide, le système de structure
générique parait bien (solution type 4) surtout si tu n'as pas envie de
refactorer le code. Le prédicat te dit si il faut appliquer la fonction
de génération sur le tétraedre et une hash_table te dit si l'élément
existe déjà pour marquer ton passage.

Ton principal problème sera quand même de savoir si tu as réussi à
parcourir tous les éléments de ton volume. Si tu le moyen de le savoir
ça me parait pas mal.

Michael


meow
Le #308900
Hello, et merci pour ta réponse aussi prompte.

D'après ce que je vois ta classe ObjetVolumique a deux responsabilité:
1 stocker les tétraedres qui la compose
Entre autre... il stocke aussi les sommets et donne un paquet de

methodes d'accés, dont des itérateurs sur les tétraedres, les sommets,
les facettes (triangles) et les arretes... Ainsi que des circulateurs
pour les tetraedres ou les triangles autour d'une arretes donnée,
etc...

2 donner l'organisation geograpghique des éléments du volume
On parlera plutot de topologie, ou de combinatoire, mais je crois que

c'est bien ça : des liens vers les voisins et des méthodes pour les
accéder facilement.

Et maintenant tu te retrouve avec un algo qui a besoin de voir ta classe
en tant que conteneur mais ne fournit pas l'interface pour.
Je ne suis pas certain de te comprendre... Ou que tu m'as compris

(j'ai l'habitude)... Alors je précises :

ObjetVolumique stocke des occurrences de classes "internes" telles que
tetraedre, triangle, arretes ou sommet. Ces classes là ont des champs
permettant d'accéder à leurs voisins, mais c'est une notion de
voisinage VOLUMIQUE. Par exemple, étant donné un triangle quelque
part, je peux avoir la liste de ses triangles voisins (au sens "qui
partagent une meme arrete") par le biais d'un circulateur.
nb : un tétraedre a toujours quatres tétraedres voisins, un triangles
a un nombre variable de triangles voisins.

ObjetSurfacique est une sorte d'alter égo pour décrire les surfaces.
On n'a pas de tétraedres, uniquement des triangles, et chaque triangle
a exactement trois voisins. Donne moi un triangle, donne moi une
arrete, et je te dis qui est mon voisin de l'autre coté.

J'ai donc un ObjetVolumique "v" dont je veux pouvoir parcourir
facilement le bord. Pour ce faire je dois le transformer en un
ObjetSurfacique "s".
Enfonçons le clou : admettons que j'ai réussi à isoler "t", un des
triangles qui constituent le bord de v, je peux facilement me promener
dans tous les triangles qui partagent "t" dans "v"... Mais ça ne me
dit pas immédiatement quel est le voisin *sur la surface*... Pour ce
faire il faut que je circule autour de l'arrete jusqu'à trouver le
prochain triangle sur la surface.

Alors oui, je pourrai dériver ObjetVolumique en
ObjetVolumiqueEtSurfacique où j'ajouterai ces fonctions d'accès
spéciales qui feraient le boulot à chaque fois... Mais ce serait un
brin lourdingue... D'autant que je vais certainement vouloir dériver
mon ObjetSurfacique lui meme pour héberger des données diverses dans
ses sommets... Bref

Pour une idée de l'algo de ObjetVolumique "v" vers ObjetSurfacique
"s" :
- on initialise avec une facette "f" en surface de "v"
- on traite la facette f :
- on marque f comme visitée
- on crée un morceau d'arrete (structure de demi arrete) pour s
qu'on attache à chaque arrete "e" de f
- pour chaque arrete "e"
- on tourne autour de l'arrete dans v jusqu'à trouver la
prochaine facette sur la surface
- si la facette a déjà été visitée on a deux morceaux d'arre tes
qu'on peut maintenant attacher
(ce faisant on résoud le problème de voisinage sur la surface
dans une dirrection donnée)
- sinon, on traite cette nouvele facette

Cet algo demande à ce qu'on puisse attacher de l'information aux
facettes et arretes de ObjetVolumique (en pratique je les ai hébergées
toutes ensemble dans les tetraedres, mais ça ne change rien)...

Tes choix sont:
1. Séparer les deux concepts: je ne sais pas si ça fait sens dans ton cas.


O_o ...Que veux-tu dire ?

2. Ajouter les fonctionalités de container à ta classe: par exemple
ajouter des itérateurs mais c'est justement ton problème


ça, si je comprends bien, c'est ce que j'ai évoqué au dessus : ajouter
les méthodes qui résolvent à chaque fois tous le parcours volumique
pour émuler le parcours surfacique (i.e. une sous partie de l'algo de
construction).

3. Ajouter des informations de l'algo dans tes classes: ce que tu as
essayé mais ça recommencera le jour ou tu aura besoin d'un autre algo


ça c'est ce que j'ai fait dans ObjetVolumique::tetraedre pour
construire des ObjetSurfacique

4. Externaliser l'information: ce que tu as voulu faire avec ta table de
hashage


ça, c'est ce que je m'apprete à faire dans VolumiqueToSurfacique, un
objet "transitoire" que je ne créerai qu'épisodiquement pour obtenir
un ObjetSurfacique qui soit le bord d'un ObjetVolumique donné

- La 1 peut se faire simplement en ajoutant un set<> dans un objet
interface (racine) avec les fonctions d'ajout qui vont bien et te donne
accès à ton volume.


Je ne te comprends pas plu... Désolé :/

- La 2 peut se faire en trouvant une heuristique de passage dans tes
tétraedres (peut être en les marquants ou en les numérotant).
ce que j'ai fait pour implémenter mon algo. J'avais envisagé de

laisser l'info à demeure dans ObjetVolumique, mais ça ne me convainc
pas à plus d'un titre.

Ca ressemble à un cas de visitor mais il te faut pour ça itérer sur tout
tes éléments.


Je vais retourner faire un tour du coté de ce design pattern, cela ne
me fera pas de mal...

Tu peux utiliser une map mais la conversion d'un pointer vers un long
est garantie (ou est ce long long ?) en tous cas ça marche.


C'est exactement le sens de ma question ! :)
Concrètement, comment fait-on ?

Ta structure peut être générique et fournir le moyen de la remplir en
parcourant tous les éléments d'un ObjetVolumique avec un prédicat e t un
inserter.


Outcha... j'ai les méninges qui commencent à fumer... :)

Ais-je été plus clair ?

Michael DOUBEZ
Le #308898
Hello, et merci pour ta réponse aussi prompte.

D'après ce que je vois ta classe ObjetVolumique a deux responsabilité:
1 stocker les tétraedres qui la compose
Entre autre... il stocke aussi les sommets et donne un paquet de

methodes d'accés, dont des itérateurs sur les tétraedres, les sommets,
les facettes (triangles) et les arretes... Ainsi que des circulateurs
pour les tetraedres ou les triangles autour d'une arretes donnée,
etc...

2 donner l'organisation geograpghique des éléments du volume
On parlera plutot de topologie, ou de combinatoire, mais je crois que

c'est bien ça : des liens vers les voisins et des méthodes pour les
accéder facilement.

Et maintenant tu te retrouve avec un algo qui a besoin de voir ta classe
en tant que conteneur mais ne fournit pas l'interface pour.
Je ne suis pas certain de te comprendre... Ou que tu m'as compris

(j'ai l'habitude)... Alors je précises :

ObjetVolumique stocke des occurrences de classes "internes" telles que
tetraedre, triangle, arretes ou sommet. Ces classes là ont des champs
permettant d'accéder à leurs voisins, mais c'est une notion de
voisinage VOLUMIQUE. Par exemple, étant donné un triangle quelque
part, je peux avoir la liste de ses triangles voisins (au sens "qui
partagent une meme arrete") par le biais d'un circulateur.
nb : un tétraedre a toujours quatres tétraedres voisins, un triangles
a un nombre variable de triangles voisins.

ObjetSurfacique est une sorte d'alter égo pour décrire les surfaces.
On n'a pas de tétraedres, uniquement des triangles, et chaque triangle
a exactement trois voisins. Donne moi un triangle, donne moi une
arrete, et je te dis qui est mon voisin de l'autre coté.

J'ai donc un ObjetVolumique "v" dont je veux pouvoir parcourir
facilement le bord. Pour ce faire je dois le transformer en un
ObjetSurfacique "s".
Enfonçons le clou : admettons que j'ai réussi à isoler "t", un des
triangles qui constituent le bord de v, je peux facilement me promener
dans tous les triangles qui partagent "t" dans "v"... Mais ça ne me
dit pas immédiatement quel est le voisin *sur la surface*... Pour ce
faire il faut que je circule autour de l'arrete jusqu'à trouver le
prochain triangle sur la surface.

Alors oui, je pourrai dériver ObjetVolumique en
ObjetVolumiqueEtSurfacique où j'ajouterai ces fonctions d'accès
spéciales qui feraient le boulot à chaque fois... Mais ce serait un
brin lourdingue... D'autant que je vais certainement vouloir dériver
mon ObjetSurfacique lui meme pour héberger des données diverses dans
ses sommets... Bref

Pour une idée de l'algo de ObjetVolumique "v" vers ObjetSurfacique
"s" :
- on initialise avec une facette "f" en surface de "v"
- on traite la facette f :
- on marque f comme visitée
- on crée un morceau d'arrete (structure de demi arrete) pour s
qu'on attache à chaque arrete "e" de f
- pour chaque arrete "e"
- on tourne autour de l'arrete dans v jusqu'à trouver la
prochaine facette sur la surface
- si la facette a déjà été visitée on a deux morceaux d'arretes
qu'on peut maintenant attacher
(ce faisant on résoud le problème de voisinage sur la surface
dans une dirrection donnée)
- sinon, on traite cette nouvele facette

Cet algo demande à ce qu'on puisse attacher de l'information aux
facettes et arretes de ObjetVolumique (en pratique je les ai hébergées
toutes ensemble dans les tetraedres, mais ça ne change rien)...

Tes choix sont:
1. Séparer les deux concepts: je ne sais pas si ça fait sens dans ton cas.


O_o ...Que veux-tu dire ?

2. Ajouter les fonctionalités de container à ta classe: par exemple
ajouter des itérateurs mais c'est justement ton problème


ça, si je comprends bien, c'est ce que j'ai évoqué au dessus : ajouter
les méthodes qui résolvent à chaque fois tous le parcours volumique
pour émuler le parcours surfacique (i.e. une sous partie de l'algo de
construction).

3. Ajouter des informations de l'algo dans tes classes: ce que tu as
essayé mais ça recommencera le jour ou tu aura besoin d'un autre algo


ça c'est ce que j'ai fait dans ObjetVolumique::tetraedre pour
construire des ObjetSurfacique

4. Externaliser l'information: ce que tu as voulu faire avec ta table de
hashage


ça, c'est ce que je m'apprete à faire dans VolumiqueToSurfacique, un
objet "transitoire" que je ne créerai qu'épisodiquement pour obtenir
un ObjetSurfacique qui soit le bord d'un ObjetVolumique donné

- La 1 peut se faire simplement en ajoutant un set<> dans un objet
interface (racine) avec les fonctions d'ajout qui vont bien et te donne
accès à ton volume.


Je ne te comprends pas plu... Désolé :/

- La 2 peut se faire en trouvant une heuristique de passage dans tes
tétraedres (peut être en les marquants ou en les numérotant).
ce que j'ai fait pour implémenter mon algo. J'avais envisagé de

laisser l'info à demeure dans ObjetVolumique, mais ça ne me convainc
pas à plus d'un titre.

Ca ressemble à un cas de visitor mais il te faut pour ça itérer sur tout
tes éléments.


Je vais retourner faire un tour du coté de ce design pattern, cela ne
me fera pas de mal...

Tu peux utiliser une map mais la conversion d'un pointer vers un long
est garantie (ou est ce long long ?) en tous cas ça marche.


C'est exactement le sens de ma question ! :)
Concrètement, comment fait-on ?

Ta structure peut être générique et fournir le moyen de la remplir en
parcourant tous les éléments d'un ObjetVolumique avec un prédicat et un
inserter.


Outcha... j'ai les méninges qui commencent à fumer... :)

Ais-je été plus clair ?



Oui, j'ai cru que ton problème était de parcourir tous les éléments de
ton volume i.e. que ta racine de persistance des objets était ta
représentation topographique et que donc tu devait les marquer pour ne
pas tourner en boucle.

En fait, si j'ai bien compris, tu ne veux parcourir que les éléments de
surfaces, l'algorithme étant initié par un élément de surface initial.

Concrètement sans parler de structure générique:
// map ou hash_map au choix
typedef map<ObjetVolumique::tetraedre*, TetraInfo> info_t

void make_surface(ObjetVolumique::tetraedre* init, info_t& info)
{
//while there is surfacique element to visit
while(init)
{
ObjetVolumique::tetraedre* next=NULL;
for(/* all connected elements elt to init */)
{
info_t::iterator it(find(elt));
if(it==info.end())
{ // elt not yet inserted
//act accordingly
info_t[elt]=TetraInfo(...);
//update next element to visit
next=elt;
}
else
{ //already inserted - act accordingly
it->method();
}
//update loop
init=next;
}
}


Maintenant cet algorithme ne te garanti pas que tous les éléments
surfaciques seront visité en fonction de la forme de la surface mais le
principe est là.

Michael


JBB
Le #308804
Bonjour,

En préliminaires, description du problème :
J'ai une classe ObjetVolumique qui me permet de représenter des
objets comme un ensemble de points, d'arretes, de triangles et de
tétraedres avec des relations d'incidences qui vont bien (c.à.d que
j'ai un moyen savoir quel triangle est une face de quel tetraedre, que
tetraedre est le voisin de qui et par quelle face, quels sont les
sommets de tel tétraedre, etc...).
Or pour certaines observations je suis amené à m'intéresser
essentiellement au "bord" de cet objet, soit donc à considérer une
classe ObjetSurfacique dont j'instancierai un objet a partir d'un
instance d'ObjetVolumique. L'algo de construction d'un objet
surfacique consiste essentiellement en une promenade dans les
tétraedres de mon objet volumique et demande à ce que je puisse
laisser des traces du parcours (suis-je déjà passé dans ce tétraedre ?
Ais-je déja créé l'arrete de mon objet surfacique correspondant a
cette arrete de l'objet volumique ? ).

Ma friche :
Jusqu'à présent, j'ai modifié les classes interne d'ObjetVolumique
(ObjetVolumique::tétraedres et Cie) afin qu'elles hébergent les
"échafaudages" de l'algo de construction d'ObjetSurfacique... Ce qui
est laid à plusieurs égards, ne serait-ce que parce qu'ObjetVolumique
n'a en définitive rien à voir avec l'algorithme en question et ne
devrait donc pas se trouver correllé avec lui...

1.) Ma question :
Je cherche un moyen d'opérer cette décorrellation !

2.) Ma seconde question : Une réponse possible
On a attiré mon attention sur les hash_map, et si je comprends bien
l'utilisation de la chose : au lieu de stocker mes infos de
construction ConstructionInfo dans les ObjetVolumique::tetraedre, je
les stockerai dans un
hash_map<ObjetVolumique::tetraedre,ConstructionInfo>.
Si cela vous semble une bonne méthode j'aurai deux autres questions :

a.) visiblement tetraedre n'est pas automatiquement géré pour la
fonction de hashage... Du coups il faudrait que j'en écrive une... Je
pensais utiliser l'adresse mémoire du tétraèdre pour me ramener à une
fonction de hachage qui, elle, serait déjà défine... Mais bon...
tretraedre* n'est à priori pas plus géré que tétraèdre, il faudrait
donc que je fasses une conversion vers un "type intégral"(?) géré...
C'est quoi un type intégral ? Comment je peux faire ça ? Une autre
idée ?

b.) design encore : pour l'implémentation de mon algo j'envisage une
classe VolumiqueToSurfacique qui contiendrait un hash map comme décrit
ci dessus... ça parrait correct ?
A la limite, il peut etre meme que j'englobe ce hash-map dans une
structure qui me donne une interface plus spécifique à mon algo...
genre un TetraInfos qui aggregerait un hash map et fournirait des
fonctions du type isTetraSeen(tetraedre), getTetraEdge(tetraedre)
etc...

Qu'est ce que tu appelle 'une promenade'?

Quelle regle defnit cette promenade?
1) je prends les tetraedres un par un au hazard?
2) j'ai une liste qui me permet de parcourir rous les tetraedres?
3) je prends un tetraedre, et je suis capable de trouver le suivant (les suivants) ?
4) que fais tu quand tu tombe sur un tetraedre dans lequel tu est déjà passé?

J'ai l'impression que tu veux faire un parcours recursif, en partant d'un tetraedre qui peut avoir plusieurs suivant.
Dans ce cas avoir un
set<Tetraedres *> listeTetraedresDejaTraites;
que tu passe par refenrece (ou en donnée membre) me parait une bonne idée.

parcourir( set<Tetraedres *> & listeTetraedresDejaTraites, Tetraedre * tetraedre){
if (tetraedre.find(tetraedre) == tetraedre.end()) {
tetraedre.insert(tetraedre);
//pour tous les suivants
parcourir(listeTetraedresDejaTraites,tetraedresuivant);
}
}

Autres remarques:
si tu as beaucoup de Tetraedre ( 100000 ?), un parcours recursif n'est peut etre pas l'idéal
if faut alors le remettre a plat.

Deuxieme remarque:
comment connait tu le(s) suivants du tetraedre.
soit tu l'as directemet a partir du tetraedre et donc pas de probleme
par contre si cette info depend de ObjetVolumique ( et qut tu n'a pas envie de savoir comment il fait)
soit tu rajoute une methode getsuivants() sur ton objet
sinon le pattern 'visitor' parait un bon candidat

Michael DOUBEZ
Le #308798
Bonjour,

En préliminaires, description du problème :
J'ai une classe ObjetVolumique qui me permet de représenter des
objets comme un ensemble de points, d'arretes, de triangles et de
tétraedres avec des relations d'incidences qui vont bien (c.à.d que
j'ai un moyen savoir quel triangle est une face de quel tetraedre, que
tetraedre est le voisin de qui et par quelle face, quels sont les
sommets de tel tétraedre, etc...).
Or pour certaines observations je suis amené à m'intéresser
essentiellement au "bord" de cet objet, soit donc à considérer une
classe ObjetSurfacique dont j'instancierai un objet a partir d'un
instance d'ObjetVolumique. L'algo de construction d'un objet
surfacique consiste essentiellement en une promenade dans les
tétraedres de mon objet volumique et demande à ce que je puisse
laisser des traces du parcours (suis-je déjà passé dans ce tétraedre ?
Ais-je déja créé l'arrete de mon objet surfacique correspondant a
cette arrete de l'objet volumique ? ).

Ma friche :
Jusqu'à présent, j'ai modifié les classes interne d'ObjetVolumique
(ObjetVolumique::tétraedres et Cie) afin qu'elles hébergent les
"échafaudages" de l'algo de construction d'ObjetSurfacique... Ce qui
est laid à plusieurs égards, ne serait-ce que parce qu'ObjetVolumique
n'a en définitive rien à voir avec l'algorithme en question et ne
devrait donc pas se trouver correllé avec lui...

1.) Ma question :
Je cherche un moyen d'opérer cette décorrellation !

2.) Ma seconde question : Une réponse possible
On a attiré mon attention sur les hash_map, et si je comprends bien
l'utilisation de la chose : au lieu de stocker mes infos de
construction ConstructionInfo dans les ObjetVolumique::tetraedre, je
les stockerai dans un
hash_map<ObjetVolumique::tetraedre,ConstructionInfo>.
Si cela vous semble une bonne méthode j'aurai deux autres questions :

a.) visiblement tetraedre n'est pas automatiquement géré pour la
fonction de hashage... Du coups il faudrait que j'en écrive une... Je
pensais utiliser l'adresse mémoire du tétraèdre pour me ramener à une
fonction de hachage qui, elle, serait déjà défine... Mais bon...
tretraedre* n'est à priori pas plus géré que tétraèdre, il faudrait
donc que je fasses une conversion vers un "type intégral"(?) géré...
C'est quoi un type intégral ? Comment je peux faire ça ? Une autre
idée ?

b.) design encore : pour l'implémentation de mon algo j'envisage une
classe VolumiqueToSurfacique qui contiendrait un hash map comme décrit
ci dessus... ça parrait correct ?
A la limite, il peut etre meme que j'englobe ce hash-map dans une
structure qui me donne une interface plus spécifique à mon algo...
genre un TetraInfos qui aggregerait un hash map et fournirait des
fonctions du type isTetraSeen(tetraedre), getTetraEdge(tetraedre)
etc...

Qu'est ce que tu appelle 'une promenade'?

Quelle regle defnit cette promenade?


C'est aussi ce que j'avais compris mais ce ne semble pas être sont problème.

if faut alors le remettre a plat.

Deuxieme remarque:
comment connait tu le(s) suivants du tetraedre.
soit tu l'as directemet a partir du tetraedre et donc pas de probleme
par contre si cette info depend de ObjetVolumique ( et qut tu n'a
pas envie de savoir comment il fait)
soit tu rajoute une methode getsuivants() sur ton objet
sinon le pattern 'visitor' parait un bon candidat



D'après son autre post, pas tant que ça car il ne veut pas parcourir
tous les éléments de son volume mais seulement ceux en surface.
Bien sûr, on peut passer un prédicat Next qui permet de déterminer le
parcours à suivre mais alors l'algo générique est stupide.
De plus, comme il a besoin d'une structure qui lui sert a savoir si il
est déjà passé sur un tetraedre etqu'il a besoin de stocker des
information sur les tetraedres, il peut donc soit:
1. utiliser deux structure (un set<> et une map<>) (donc multiplie les
recherches par 2)
2. utiliser une seule structure (mais c'est d'une génericité douteuse).

Etant donnés ces éléments, un algo generique de visitor ne me parait pas
utile. Il peut très bien définir une fonction for_all_surf<>() qui a
comme argument un type d'info a stocker par surface et un générateur de
cette info. Et encore, AMA, il n'aurais pas forcément intérèt à le faire
tout de suite (seulement si il a besoin du même algo de parcours pour
autre chose).

Michael


meow
Le #309400
Désolé, je suis un peu au feu en ce moment, je prendrai le temps de
voulire et de vous répondre plus en détail dès que cela se sera calm é.
En attendant, merci pour votre attention et vos conseils. J'ai lu les
dernières réponses en diagonale et j'y ai vu des éléments de répo nse à
des questions que je n'avais pas posées (sur l'implémentation de
l'algo en lui meme) mais qui se posent pourtant... En attente donc de
pouvoir les lire avec plus d'attention.

--ben
Publicité
Poster une réponse
Anonyme