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

 
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 ?

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

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  
J'attends d'avantage d'explications...Ainsi qu'un algorithme correnspondant a mon probleme
merci

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.

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.

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

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

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    

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

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

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) :

 
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) :

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    
 
voici ce que j'ai fé jusqu'à prensent...dites moi ce que vous en pensez..
c la triangulation et la matrice d'adjacence...

 
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

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