[Matlab]Triangulation..Arbre...DFS...

Triangulation..Arbre...DFS... [Matlab] - Algo - Programmation

Marsh Posté le 26-03-2006 à 23:41:44    

bonjour ts le monde...Je c pas si qq1 pourrais m'aider...mais je v vous expliquer mon probleme comme meme...
Deja c en matlab que ts ce deroule...J'ai une surface donnée(polygone)...dans un premier temps je ferais la triangulation(delaunay)...puis, je vais extraire un arbre (chaque noeud represente un triangle) et le parcourir en utilisant l'algorithme de parcours en profondeur(Depth Firt Search)...
C ça en gros ce que je veux faire...J'ai du mal a extraire l'arbre pour le parcourir par la suite(a vrai dire j'ai trop chercher mais j'ai pas d'idee pour le faire)....
Donc si qq1 pourrais m'aidee ce serais genial...
merci d'avance

Reply

Marsh Posté le 26-03-2006 à 23:41:44   

Reply

Marsh Posté le 27-03-2006 à 10:13:16    

Citation :

je vais extraire un arbre (chaque noeud represente un triangle)


 
c'est plutôt un graphe que tu veux, non ? Je ne vois pas quel type d'arbre tu pourrais construire à partir d'une triangulation... déjà, quelle serait la racine de ton arbre ?

Reply

Marsh Posté le 28-03-2006 à 00:43:35    

En fait, pour plus de precision, le but est de faire deplacer une machine (robot par exp) de façon a couvrir toute une surface polygonale donnée....
 
Les etapes sont:
-Trianguler la surface(delaunay)
-Parcourir l'arbre representatif de cette surface(Algorithme de parcours en profendeur) comme ça on se deplace sur toute la surface
-Parcourir chaque triangle
 
c ça en gros ce qu'il faut faire :sweat: ...
 
Je crois je me ss mal expliqué en parlant d'extraction d'arbre et ts....c prcq je comprend mal ce point...a mon avis on doit extraire un arbre pour le parcourir par la suite :heink: ...j'ai des doutes la dessus pcq lors de ma recherche sur le net, on parle de parcours d'arbre directement sans parler d'extraction d'arbre ou autre...Je comprend pas :??:  
 
merci

Reply

Marsh Posté le 28-03-2006 à 09:07:31    

Je comprends toujours pas comment tu vas pouvoir construire un arbre à partir d'une triangulation : pour moi, une triangulation a une structure de graphe (par exemple chaque sommet du graphe est un triangle ; deux sommets sont reliés par une arête si les triangles correspondants possèdent un côté commun). Mais pour trouver un arbre là dedans, il te faudrait une notion de hiérarchie, et je ne vois pas où tu vas a trouver.
 
Ceci dit, si ton but est de parcourir toute ta surface, tu peux aussi le faire en parcourant un graphe plutôt qu'un arbre.

Reply

Marsh Posté le 28-03-2006 à 13:01:19    

Citation :

Je comprends toujours pas comment tu vas pouvoir construire un arbre à partir d'une triangulation : pour moi, une triangulation a une structure de graphe (par exemple chaque sommet du graphe est un triangle ; deux sommets sont reliés par une arête si les triangles correspondants possèdent un côté commun). Mais pour trouver un arbre là dedans, il te faudrait une notion de hiérarchie, et je ne vois pas où tu vas a trouver.
 
Ceci dit, si ton but est de parcourir toute ta surface, tu peux aussi le faire en parcourant un graphe plutôt qu'un arbre.


 
Ts ce que t'as dis est juste.....Comme j'ai dis ds mon dernier poste j'ai du mal a comprendre ça....
Ton idee est bien ce que j'ai lu qq part sur le net.....et que j'ai pas compris :sweat:  
J'attends d'avantage d'explications...Ainsi qu'un algorithme correnspondant a mon probleme
merci

Reply

Marsh Posté le 29-03-2006 à 13:42:32    

Peut être ... qu il s agit de définir la position du robot comme racine de l arbre, et de construire un arbre à partir d un parcours en profondeur du graphe..?
 
Le robot semble ``explorer`` la surface à partir de son point de départ.

Reply

Marsh Posté le 29-03-2006 à 13:52:19    

C'est ce que je me dis aussi.
 
Mais à ce moment là, ça ne sert à rien de construire un arbre : le simple parcours de ton graphe permet déjà d'explorer tous tes triangles.

Reply

Marsh Posté le 29-03-2006 à 14:15:10    

> Mais à ce moment là, ça ne sert à rien de construire un arbre : le simple parcours de ton graphe permet déjà d'explorer tous tes triangles.
 
Exact, sauf si le but est de donner l impression que le robot revient vers son point départ quand il explore. Ça donne un arbre binaire dans lequel le hauteur d un noeud est fonction du nombre de triangles qui le sépare du point de départ.

Reply

Marsh Posté le 29-03-2006 à 15:00:19    

L'arbre est necessaire pour guider le robot...pour qu'il puisse par exp revenir a sa bese(a determiner)pour recherger ses batteries....On peut biensur faire un petit test (de convexité) pour verifier que s'il ya moyen d'aller directement au point desiré a la place de suivre l'arbre et faie un plus long chemin

Reply

Marsh Posté le 29-03-2006 à 15:02:00    

Citation :

Exact, sauf si le but est de donner l impression que le robot revient vers son point départ quand il explore. Ça donne un arbre binaire dans lequel le hauteur d un noeud est fonction du nombre de triangles qui le sépare du point de départ.


je comprends pas trop ce que tu veux dire : a priori, si tu construis un arbre à partir du parcours en profondeur du graphe, tu obtiendras l'arbre le plus déséquilibré possible (et même un peigne dans le cas où il est possible de parcourir tous les triangles les uns à la suite des autres sans passer deux fois par le même).
Par contre, c'est vrai que si tu construis un arbre à partir du parcours en étendue du graphe, alors là tu obtiendras un arbre aussi équilibré que possible dans lequel la hauteur de chaque noeud est la distance à l'origine.
 
 
Mais peut-être qu'on est en train de parler de choses différentes  :??:  

Reply

Marsh Posté le 29-03-2006 à 15:02:00   

Reply

Marsh Posté le 29-03-2006 à 15:02:02    

L'arbre est necessaire pour guider le robot...pour qu'il puisse par exp revenir a sa base(a determiner)pour recherger ses batteries....On peut biensur faire un petit test (de convexité) pour verifier que s'il ya moyen d'aller directement au point desiré a la place de suivre l'arbre et faire un plus long chemin...

Reply

Marsh Posté le 29-03-2006 à 15:44:17    

> Par contre, c'est vrai que si tu construis un arbre à partir du parcours en étendue du graphe
 
ouais, parcours en profondeur il me semble que ça s appelle: à chaque tour tu ajoute les triangles pas encore découverts comme fils de ceux déjà parcourrus. plusieurs arbres possibles, dont certains équilibrés par distance euclidienne à l origine (racine).
 
> On peut biensur faire un petit test (de convexité) pour verifier que s'il ya moyen d'aller directement au point desiré a la place de suivre l'arbre et faire un plus long chemin...
 
Pour ça il y a des algo de plus court chemin.
 
Pour tout parcourrir de façon optimale il y a les algo de couvertures de sommets, mais qui ne donnent pas l illusion d une ``exploration`` méthodique.

Reply

Marsh Posté le 30-03-2006 à 14:43:41    

Citation :

L'arbre est necessaire pour guider le robot...pour qu'il puisse par exp revenir a sa bese(a determiner)pour recherger ses batteries....On peut biensur faire un petit test (de convexité) pour verifier que s'il ya moyen d'aller directement au point desiré a la place de suivre l'arbre et faie un plus long chemin


Voilà ce que je te propose :
1- tu construis ta triangulation
2- tu construis un graphe à partir de ta triangulation : les sommets du graphe sont les triangles de ta triangulation ; deux sommets sont reliés par une arête si les deux triangles correspondants sont voisins
3- tu construis un "arbre d'exploration" à partir d'un parcours en profondeur de ton graphe. Le parcours en profondeur de cet arbre te permet d'explorer toute ta surface en repassant le moins possible sur des triangles déjà explorés.
exemple (le triangle de base est "F" ; les numéros dans les triangles indiquent leur ordre dans le parcours en profondeur du graphe / de l'arbre) :
http://fevotte.free.fr/Downloads/triangulationProf.gif
 
4- tu construis un "arbre de retour à la base" à partir du parcours en largeur de ton graphe. Lorsque tu es dans un triangle il te suffit de remonter de fils en père pour revenir par le chemin le plus court à la base.
exemple (le triangle de base est "F" ; les numéros dans les triangles te donnent leur ordre dans le parcours en largeur du graphe / de l'arbre) :
http://fevotte.free.fr/Downloads/triangulationLarg.gif


---------------
TriScale innov
Reply

Marsh Posté le 20-04-2006 à 08:57:44    

Bonjour les amis, d'abord j'aimerais vous remercier d'avoir pris la peine de me repondre...
 
Pour etre plus clair ceci est un projet...j'y travail avec mon prof...il me dis ce que je dois faire
 
Merci comme meme pour vos suggestion(bfs a la place de dfs).....mais je dois suivre ses instructions  :ange:  
 
voici ce que j'ai fé jusqu'à prensent...dites moi ce que vous en pensez..
c la triangulation et la matrice d'adjacence...

Code :
  1. a=load ('dd.txt');
  2. x=a(:,1);
  3. y=a(:,2);
  4. plot(x,y,'+')
  5. xlabel('longitude')
  6. ylabel('latitude')
  7. grid on
  8. tri=delaunay(x,y)
  9. hold on
  10. triplot(tri,x,y)
  11. hold off
  12. %la dessous j'ai essayé d'ecrire à cote de chaque noeud
  13. %le numero correspondant(pas les coordonnées):1,2,....
  14. %mais il me passe les coordonnées!!!
  15. %plot(x,y, 'b*-')
  16. %text(x+.05,y,num2str(y))
  17. nsom = max(max(tri));
  18. ntri = size(tri,1);
  19. A = zeros(ntri);
  20. for i=1:ntri
  21.     A(tri(i,1),tri(i,2)) = 1;
  22.     A(tri(i,2),tri(i,3)) = 1;
  23.     A(tri(i,3),tri(i,1)) = 1; 
  24.     % Faire attention à la symetrie
  25.     A(tri(i,2),tri(i,1)) = 1;
  26.     A(tri(i,3),tri(i,2)) = 1;
  27.     A(tri(i,1),tri(i,3)) = 1;
  28. end


 
Toutes vos remarques sont la bienvenue....
 
Et puis si vous avez des suggestions concernant le point suivant, qui est le DFS, n'hesitez pas non plus...
 
Merci d'avance

Reply

Marsh Posté le 29-02-2012 à 16:35:41    

slt les amis je fais recherches sur la localisation indoor mon professeur me demande de faire une programmation de triangulation sur matlab mais moi je ne sais pas le faire. est ce que vous pouvez m'aider?? merci d'avance  

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed