Consulter le rapport
Contents
1. algorithme n a pas lieu d tre S il y en a deux Dijkstra semble plus indiqu et est lanc A partir de trois villes s lectionn es l algorithme se lancer Il commence par se positionner sur la premi re gare prise en param tre On cr e ensuite un tableau qui contiendra la suite d identifiants de gares symbolisant le chemin On met l identifiant du premier n ud sur la premi re case du tableau On initialise tous les n uds du graphe en tant que non visit s Puis on cr e une boucle qui va visiter tous les n uds dont les identifiants sont compris dans le tableau de visites et on v rifie s ils sont on d j t visit s ou pas gr ce leur variable de visite S ils ont t tous visit s on renvoie le tableau contenant le chemin Dans cette boucle on proc de l algorithme en tant que tel On parcourt les fils de chaque n ud et on compare les distances contenues par chaque arc entre elles qui contient la valeur de la distance On retient ensuite l arc qui contient la distance la plus courte puis on se positionne sur le n ud point par cet arc On sort de la boucle puis on y rerentre pour ce nouveau n ud L algorithme se d roule ainsi jusqu ce que tous les n uds de la premi re boucle soient parcourus 12 6 2 opt Principe et fonctionnement A quoi sert il L algorithme dit 2 opt est un algorithme d optimisation Dans notre cas il r cup re le r sultat du PVC puis essaie2. II place en point de d part la position de la gare qui se trouve dans le n ud principal et pour chacun de ces successeurs il r cup re la position de la gare Ainsi il ne reste plus qu tracer une simple droite 15 entre ces deux points Une droite se trace facilement gr ce GL_LINES et aux coordonn es des deux points Nous avons aussi trouv utile d afficher sur la map la distance de chacun des rails Nous l avons inscrite au milieu de chaque rail Pour cela il a donc fallu calculer les coordonn es du milieu du segment que repr sente le rail gr ce la formule g om trique suivante Xmilieu X1 X2 2 Ymilieu Y1 Y2 2 De plus pour permettre de distinguer dans quelle direction se dirige un rail nous avons rajout au bout de ce dernier un petit cercle gris 3 L interface Glui Fonctionnement A propos de GLUI Voici la d finition de Wikip dia OpenGL User Interface Library GLUI est une biblioth que en C qui se combine avec celle d OpenGL utility toolkit GLUT et qui fournit diverses routines pour cr er l interface d un programme enti rement avec OpenGL L interface est alors ind pendante du syst me d exploitation et du gestionnaire de fen tres Cette biblioth que sous licence GNU LGPL permet de compl ter la biblioth que de gestion de fen tres OpenGL GLUT en apportant le support de divers l ments de contr le tels que les boutons les cases cocher les zones de texte ditables e
3. clic droit est utilis pour ce programme Chaque clic droit s lectionne une ville et la garde en m moire Pour s lectionner les n gares que vous voulez relier faites tout d abord un clic gauche pour vider votre tableau de villes s lectionn es Puis faites un clic droit sur chacune des gares que vous voulez relier Ensuite clique sur le bouton correspondant Comme pour l l ment pr c dent le chemin sera affich sur la carte par le changement de couleur de chaque gare travers e par application D terminer et afficher du r seau accessible Cette fonction est utile si vous d sirez d terminer si le graphe est auto accessible Pour ce faire c est tr s simple il suffit de cliquer sur le bouton correspondant Dans la console de messages s affichera alors la conclusion savoir si votre r seau est auto accessible ou non 19 3 Edition Ajouter une ville Ajouter une ville est assez simple Il suffit de mettre le nom qu on veut donner la ville dans la zone de texte de cliquer sur le bouton Ajouter une ville puis de cliquer sur la carte o l on veut la placer La console de message vous expliquera si l ajout a bien fonctionn e ou pas La ville s affichera en cons quence sur la carte en rouge avec c t d elle son nom Supprimer une ville Pour supprimer une ville il suffit de cliquer sur le bouton correspondant puis comme demand dans la console de message cliquer sur la v
4. d en optimiser le r sultat Comment fonctionne t il Comme dit pr c demment il r cup re le r sultat d un algorithme en permute successivement les membres pour d terminer si un meilleur r sultat n est pas possible Une explication de son fonctionnement adapt notre cas est donn e juste apr s Impl mentation Utiliser le 2 opt dans sa forme la plus pure et la plus optimis e est un gros challenge En effet il fonctionne de cette fa on Je prends le tableau cr par 2 opt et je proc de mon algorithme Dans une double boucle je me balade deux fois dans mon tableau de cette fa on For i 0 i lt taille i for j i 1 j lt taille j J change dans cette boucle les trajets ce qui veut dire que je n change pas les directement 1 3 Soient des villes qui selon un parcours sont comme a 0 gt 1 gt 2 gt 3 gt 4 gt 5 gt 6 gt 7 gt 8 gt 9 Alors si j change entre 2 et 7 je fais ce type d change 0 gt 1 gt 7 gt 6 gt 5 gt 4 gt 3 gt 2 gt 8 gt 9 Algorithmiquement parlant Soient p1 inverser avec p2 RENVERSEMENT l ment_avant_p1 point sur p2 p1 point sur element_apres_p2 gain dist p1 element_apr s_p1 dist p2 element_apres_p2 dist l ment_avant_p1 p2 dist p1 point sur element_apres_p2 Donc l algo serait en gros For i 0 i lt taille i for j i 1 j lt taille j RENVERSEMENT si le gain est lt 0 alors le chemin est plus court et il faut garder le renversem
5. la suppression puis de cliquer sur chacune des gares reli es Attention comme dit pr c demment l ordre de clic sur les gares est d terminant du rail que vous 20 V R sultats obtenus par notre application Nous allons dans cette partie vous pr senter les r sultats de notre travail en pr sentant par des captures d cran ce que nos algorithmes apportent et analysant ce que nous avons r ussi faire A Les calculs 1 La carte Le r seau ferroviaire se situe dans une r gion r gion que nous devions repr senter par une carte constitu e de diff rents types de terrains Nous avons souhait une carte simple pour visualiser tr s bien les diff rents terrains et gares et galement de taille raisonnable pour ne pas ralentir les calculs et ne pas cacher l interface GLUI Nous en sommes venus obtenir deux cartes repr sentant plus ou moins un m me territoire Nous avons tout d abord une carte assez d taill e avec des contours lisses et d assez grande taille Nous affichons cette carte en vraies dimensions ce qui permet un affichage assez agr able Malheureusement le d tail de cette carte peut parfois amener certains ralentissements qui peuvent parfois tre tr s g nant Nous avons donc repris cette carte et en avons con u une autre plus petite D 1 et moins d taill e qui permet une utilisation optimale du programme amp 1irk dmeIEere lest 4 Wen E PUETICU Le Si 1 AONENE are
6. une premi re partie nous vous exposerons les outils de base du logiciel qui permettent de lancer une image ou la sauvegarder Le logiciel permet deux types d interactions que nous qualifierons d affichage et d dition Parce qu une capture d cran parle mieux que des mots vains voici quoi ressemble l interface GLUI son lancement Console de message Gare data gares gar Rail datasrails ral 18 Map images map ppm Charger une region et ses villes Sauvegarder C Afficher F L Edition P Guit 1 Pour commencer Lors du lancement du programme aucune carte n est charg e La premi re chose faire est de clique sur le bouton Charger une r gion et ses villes apr s avoir rentr l adresse des fichiers de gares ville et carte d sir s Par d faut les fichiers d images se trouvent dans le dossier images et ceux de rails et de gares dans le dossier data Une fois ceci fait la r gion se charge ainsi que ses villes et ses gares Juste en dessous du bouton de chargement se trouve un bouton de sauvegarde Vous pouvez tout moment en cliquant sur ce bouton sauvegarder votre carte ainsi que vos fichiers de rails et de villes La sauvegarde remplacera les fichiers existants Nous tenons aussi mentionner dans cette partie la zone de texte qui se situe tout en haut de l application Nous appellerons cette zone la console de message Afin de rendre notre application ind pendante
7. Mod lisation d un r seau ferroviaire Familiarisation avec la structure de graphe Utilisation de fonctions de dessin 2D OpenGL Codage des algorithmes fondamentaux des graphes et de synth se d images D couverte d une API d interface utilisateur GLUI Introduction Dans le cadre de notre second semestre en premi re ann e l cole d ing nieur IMAC il nous a t demand de r aliser un projet de grande ampleur consistant la r alisation d un r seau ferroviaire Deux domaines sont r unis pour r aliser ce projet le premier tant l algorithmie avanc e et le deuxi me la synth se d image Notre travail se divise en deux parties une plus dirig e vers le rendu et l autre vers les algorithmes Nous devons donc mettre en place un programme qui permettra d afficher un r seau ferroviaire sur une carte faite par nos soins et coder des algorithmes fondamentaux pour r soudre les principales probl matiques qui peuvent se poser lors de la cr ation d un r seau Pour ce faire nous commencerons par positionner les enjeux et les probl matiques du projet expliquer nos besoins et les r sultats que nous souhaitons obtenir pour ensuite d crire la structure de notre projet la justification du d coupage des fichiers et de nos fonctions Nous d taillerons ensuite plus en d tail le projet en lui m me Nous parlerons ainsi des choix faits et du morcellement des fichiers de notre projet puis nous parleron
8. de l utilisation de la console nous avons via cet outil affich tous les messages que nous faisions passer habituellement dans la console Elle affiche les instructions d utilisation du logiciel ou les messages d erreur comme s lectionnez une seconde villen ou vous n avez pas s lectionn assez de gare 2 Afficher Calcul du kilom trage total Si vous voulez savoir en un clic le kilom trage total du r seau ferroviaire il suffit de cliquer sur ce bouton La valeur sera affich e en kilom tres dans l espace d affichage juste en dessous du bouton D termination des gares accessibles en n coups Cet outil permet de calculer les gares accessibles en n coups d termin s par l utilisateur Pour ce faire il suffit de rentrer la valeur dans le champ texte contre le bouton cliquer sur la ville de laquelle on d sire partir puis cliquer sur le bouton S afficheront alors sur la carte toutes les villes qui sont accessibles au bout des n coups mis en param tre Calcul du plus court chemin entre deux gares Pour calculer le plus court chemin entre deux gares il suffit de cliquer sur le bouton correspondant Ensuite cliquer sur la premi re puis la seconde gare Les gares travers es par ce parcours changeront alors de couleur sur la carte vous affichant le chemin La distance calcul e quand elle sera affich e dans la console de message Calcul du plus court chemin reliant n gares Le
9. e clic de la souris sur les boutons ou sur la carte et lancer l algorithme ou la fonction qui correspond B Conception et structuration des fichiers Durant tout le d veloppement du projet nous avons port une attention particuli re la conception de celui ci Nous avons s par au maximum les donn es r alis de petites fonctions pour viter tout redondance dans le code et fortement privil gier l utilisation des structures Voici la description de chacun des fichiers gare c gare h contient la structure gare qui comprend son indice son nom l indice de la ville et un pointeur vers la ville dans laquelle elle se trouve ses coordonn es ce qui va permettre de facilement l afficher sur la map et ainsi qu un flag visite qui sera utile dans plusieurs algorithmes En ce qui concerne les fonctions ce sont des fonctions utilitaires qui permettent de r cup rer une gare partir de l id d une ville une gare partir de son id d ajouter une gare dans le graphe ou bien encore de savoir si une gare est desservie ou non Ville c ville h contient la structure ville qui comprend son indice son nom le nombre de gares qu elle abrite 0 ou 1 ainsi que sa position sur la map En ce qui concerne les fonctions ce sont des fonctions utilitaires qui permettent de r cup rer une ville par son id ou d ajouter une ville dans le graphe formes c formes h ces fichiers comportent des fonctions qui permettent de dessiner des fo
10. e la distance vers le sommet ajout e la distance entre ce sommet et ce successeur alors on remplace dans le tableau des distances sa valeur par cette derni re op ration Dans ce cas un chemin plus court est donc trouv si non rien n est chang dans le tableau En plus d obtenir toutes ces distances nous souhaitons m moriser le chemin qu il faut parcourir Pour ce faire il suffit d ajouter un tableau de pr d cesseurs Il contiendra pour chaque gare l indice de la gare pr c dente la plus proche En pratique d s que l on trouve un chemin plus court que l on met jour le tableau des distances alors dans le tableau des successeurs on ajoute l indice du sommet visit dans la case concernant le successeur trait De cette fa on pour retrouver le chemin il suffit de prendre la ville d arriv e choisie et de remonter le chemin gr ce aux indices L affichage Ce chemin doit tre bien affich sur la carte on doit donc voir les rails concern s appara tre de couleur diff rente Nous avons rajout dans la fonction qui dessine les rails une condition Si la liste contenant les gares du plus court chemin n est pas vide donc que la fonction a t appel e alors les rails reliant les gares concern es sont affich s d une couleur diff rente 11 5 Pvc Principe et fonctionnement A quoi sert il Le Probl me du Voyageur de Commerce PVC tient son explication dans son nom A l poque o les voyages et transpor
11. elmGare 1 1 garadDurGare f g MmT ware ea L algorithme du plus court chemin permet comme il a t dit plus haut de trouver partir de la s lection de deux gares le chemin le plus court les reliant Apr s avoir cliqu sur le bouton permettant de calculer ce chemin l utilisateur est invit s lectionner deux gares Une fois le calcul demand un certain temps d ex cution est n cessaire pour afficher le r sultat Dans la grande carte le temps se compte en secondes tandis que pour la petite l affichage arrive en moins d une seconde Le temps de calcul ne varie pas suivant la longueur du chemin Une fois le calcul effectu les rails formant le chemin demand apparaissent en rouge comme ci dessous amp tirk 20e omteGare eg roi yaga PSE 1440 dem e an 0 De el batbadoare LONENE are 070 ielmGare 1590 i 2220 paradDurGare rT i Pinas Mrtbtzarg PT En rouge le plus court chemin entre ComteGare et MinasTirithGare Cette fonctionnalit permet d afficher les gares accessibles apr s n changements depuis une gare s lectionn e par l utilisateur Une fois la gare s lectionn e et le n indiqu le temps de r ponse est galement assez long Suivant la carte ce temps est plus ou moins grand Nous avons toujours un temps de r ponse plus long pour la joli carte mais le temps pour la plus petite n est pas diminu de beaucoup le temps pass attendre est tout de m me no
12. ent L algorithme au jour ou nous crivons n est pas totalement impl ment Cependant nous avons dans un souci de simplicit enlev deux optimisations Celle du renversement qui consiste une permutation pure et simple des deux gares Celle du gain nous calculons chaque tape la distance totale du parcours et non le gain local r alis par la permutation Nous somme conscients de cette entorse mais nous avons estim qu il faut mieux proposer un algorithme qui fonctionne m me s il n est pas optimis que rien du tout 7 Auto accessibilit Principe et fonctionnement A quoi sert il Cet algorithme semble tre un algorithme essentiel dans la mise en place d un r seau Il est en effet impensable de cr er un r seau qui ne permet pas chaque gare d tre reli e toutes les autres Ainsi pour l utilisation de certaines fonctions il est utile de savoir si de n importe quel gare o on lance la fonction il est possible d atteindre toutes les autres gares Une gare est dite auto accessible s il est possible d atteindre toutes les autres gares partir d elle m me Un r seau est auto accessible si de toutes les gares du r seau il est possible d atteindre toutes les autres gares du r seau C est l algorithme que nous avons voulu mettre en place Comment fonctionne t il Le principe de l algorithme n est pas tr s complexe Il suffit de parcourir chacun des l ments du graphe de
13. entre deux points Techniquement il consiste calculer en tout points du segment qui relie les deux points le pixel le plus optimal allumer pour repr senter ce point afin au final de r aliser la droite la plus pr cise possible Impl mentation Dans notre cas nous avons utilis cet algorithme pour d terminer par quel pixel passe un rail et ainsi r cup rer la valeur de ces pixels Le fait de conna tre la valeur des pixels par lesquels la droite passe nous a permis deux choses calculer le kilom trage entre deux gares A chaque valeur d un pixel correspond une certaine distance Il suffit donc de sommer les distances correspondantes de chaque pixel pour obtenir le kilom trage total du rail d tecter si un rail passe par la mer Nous lan ons l algorithme et si l on passe par un pixel qui correspond la mer nous retournons une valeur d erreur A chaque fois le principe de l algorithme est le m me Il faut tout d abord d terminer l orientation de la droite qui relie le point de d part celui de l arriv e Suivant cette orientation on d coupe l algorithme en deux parties Une pour l incr mentation selon l axe des x et une pour Taxe des y Selon l axe de la pente on incr mentera x ou y et l on allumera le nouveau pixel avec sa nouvelle coordonn e Cette incr mentation se fera lorsque les valeurs r elles du point auront d pass une certaine limite d erreur Lorsque cette erreur sera trop gr
14. errain pour pouvoir soit m me faire sa carte 28
15. est auto accessible B L dition L autre aspect de notre programme est le c t dition Il est en effet possible d diter volont le r seau ferroviaire Il est possible d ajouter des villes des gares des rails ou bien de les supprimer L un des aspects les plus int ressants de cette partie est la cr ation de rails Nous avons choisi de passer par l interface graphique directement et en temps r el le rail est affich un bout tant positionn e sur la gare de d part et le second sur le pointeur de la souris suivant ses mouvements 26 omteGare SEO ATI 2 GE CLR Se butlepstg 1440 E 2810 1960 Bt Ee ZEN LONENE are ALFA slelmGare 1590 2220 garadDurGare er LU a Miz Lrtbtaare Ici le rail de droite est en train d tre cr e par l utilisateur malheureusement la souris n a pas t conserv e par le screenshot Le suivi de la souris par le rail tendance tre parfois lent avec la grande map Par contre tout est tr s fluide et rapide avec la map plus petite Parmi les autres fonctionnalit s nous avons la cr ation d une ville ou d une gare il suffit de cliquer sur l endroit souhait puis d entrer le nom dans l interface GLUI C est une action qui prend effet imm diatement La suppression des rails et des villes s effectue en cliquant sur les villes concern es ces actions sont galement imm diates 27 Conclusion Ce projet nous a permis de mettre en
16. faire un parcours et de v rifier la fin de chaque parcours si l on a bien travers tous les n uds du graphe Si tel est le cas alors le graphe est dit auto accessible Sinon cela veut dire qu au moins un des n uds ne peut pas atteindre tous les autres Et donc que le graphe n est pas auto accessible Impl mentation l impl mentation n a pas t tr s complexe Nous avons r alis deux fonctions une de parcours en largeur et une comprenant l algorithme proprement parler La fonction de parcours en largeur est quasiment la m me qu un parcours en largeur normal sauf qu elle a t dot e d un compteur qui s incr mente chaque travers e de ville Elle renvoie la valeur du compteur La fonction d auto accessibilit en elle m me parcourt chaque n ud du graphe Pour chaque n ud elle lance le parcours en profondeur et r cup re la valeur renvoy e Elle compare cette valeur renvoy e avec la taille du graphe Si la valeur est inf rieure la taille du graphe cela veut dire que le n ud en question n est pas auto accessible il ne peut pas acc der tous les autres n uds et donc que le graphe n est pas auto accessible La fonction renvoie imm diatement 1 qui correspond la valeur non accessible al A la fin de l algorithme si tous les n uds ont t visit s et si chacun d eux est auto accessible alors la fonction renvoie 0 14 IV Application interactive et Guide de l Utilisateu
17. gr ce la biblioth que GLUT pour la partie purement graphique openGL et de la biblioth que GLUI pour la mise en place des contr les boutons zone de saisie Ces derniers permettent une meilleur interactivit avec l utilisateur que par exemple l utilisation du terminal Au lancement du programme seul la fen tre de contr le GLUI s ouvre L utilisateur peut ensuite soit charger les fichiers de configurations par d faut soit indiquer le chemin d autres fichiers Les fichiers de configuration sont les fichiers gares gar qui contient les villes et les gares nous avons choisis de ne g rer qu une seule gare par ville N anmoins une ville peut ne pas contenir de gares rails ral qui contient les liaisons entres les diff rentes gares map ppm qui est une image ppm en niveau de gris et qui repr sente le terrain afficher Dans un premier temps l application va lire les fichiers Si ils sont coh rents v rification par exemple qu un rail ne passe pas par la mer elle va construire deux objets la liste des villes et le graphe qui va repr senter notre r seau Une fois le graphe charg l application va afficher le terrain Ensuite le programme va parcourir le graphe et dessiner la position des villes et des gares crire leurs noms et puis les relier entre eux gr ce la fonction de tracer de droite d openGL entre deux points Maintenant que l ensemble de l application est construite le programme va couter chaqu
18. ia eaa aaae ai aa oaa aa a aa aeae ATR 16 Guid de l utilisateur sirsiran aa E E E E ES 18 1 Pour comm h er ssasiti n nt lire dant ENEE EEEESAEEEEEAEEEE ESATEN EALE 18 KEE tte EE 19 D EdITON paee a de Ds a ee med 20 R sultats obtenus par notre application sisi 21 LescpaleOlg e a DEENEN 21 USR R A d 21 25 L PIUS ee legt EE 22 3 lechang ment de Gares irinntinniren aaea EAA E e dites EE 23 D ZS LE PE EE EE 24 5 Le calcul du kilom trage total iii 25 6 Gares auto accessibles ENEE 26 CCI IOMR a n ena bbeg 26 I Positionnement du probl me A Quels enjeux L enjeu principal de notre projet est de r aliser la simulation d un r seau ferroviaire sous forme logicielle qui en permettra une gestion virtuelle Pour ce faire le logiciel devra fournir les outils de calculs et de d termination de chemin essentiels pour r pondre aux principaux probl mes d un r seau ferroviaire Afin d tre utilisable de fa on plus g n rique ce logiciel devra aussi permettre l dition du r seau ferroviaire savoir l ajout de gares de villes de rails ainsi que leur suppression pour r pondre aux probl mes relatifs au cas de figure de l utilisateur Enfin de fa on ce que ce logiciel soit plus ergonomique et utilisable il devra permettre une gestion graphique et minimiser l utilisation de la ligne de commande B Les difficult s g rer On s aper oit ainsi rapidement que le projet demande
19. ille que vous d sirez N oubliez pas que pour supprimer une ville il faut que celle ci ne contienne pas de gare Si tel est le cas supprimez d abord la gare contenue voir ci dessous Ajouter une gare Pour ajouter une gare il suffit de mettre le nom que vous voulez lui donner dans la zone de texte correspondant sur l interface glui Ensuite cliquez sur ajouter une gare et cliquez sur la ville laquelle vous voulez ajouter la gare Faites tout de m me attention ce que cette ville ne contienne pas d j de gare Si tel est le cas la console de message vous le rappellera Supprimer une gare Pour supprimer une gare il faut auparavant tre certain que celle ci ne soit pas reli e une autre gare Si tel est le cas supprimez d abord le rail voir ci dessous Sinon cliquez simplement sur le bouton de suppression de gare puis sur la gare de la carte que vous voulez supprimer Relier deux gares Pour relier deux gares il vous faut simplement cliquer sur le bouton correspondant puis sur la premi re et la seconde gare que vous voulez relier Attention les rails que l on ajoute tant orient s l ordre dans lequel vous s lectionnez vos gares est d terminant La premi re correspond la gare de d part et la seconde la gare d arriv e Une petite boule blanche dessin e sur le rail symbolise l orientation de celui ci Supprimer un rail Pour supprimer un rail il suffit de cliquer sur le bouton correspondant
20. osse alors le pixel en question qui contient une valeur enti re sera incr ment en l axe correspondant 10 4 Plus court chemin entre deux gares Notre programme doit pouvoir afficher le plus court chemin reliant deux gares Pour ce faire l utilisateur s lectionne deux gares et les rails emprunter apparaissent alors clairement Dijkstra Pour mettre en place cette fonctionnalit nous avons utilis l algorithme de Dijkstra Cet algorithme permet de calculer les plus courts chemins entre une gare et toutes les autres Il en r sulte donc un tableau de distances Voici les tapes suivre pour cet algorithme Tout d abord le plus important est donc le tableau de distances il contient dans chaque cas la distance entre la gare de d part et gare concern e par cette case il est initialis 1 partout sauf pour la gare de d part qui est mise 0 En plus de ce tableau nous avons besoin de deux piles qui permettront de stocker les gares que nous visitons La premi re pile V contient les sommets que nous avons visit s Dans l autre pile S se trouve au d but tous sommets L commence r ellement le travail On commence par prendre le sommet de S qui a la distance la plus faible dans le tableau des distance ce sera donc au premier tour le sommet de d part on le d pile de S et on l empile dans V Ensuite on parcourt tous les successeurs de ce sommet et on teste Si la distance vers ce successeur est plus grande qu
21. pratique certaines des comp tences que nous avions acquises ce semestre Dans le domaine de l algorithmie nous avons pu mettre en place et coder des algorithmes fondamentaux et les tester sur un probl me r el le r seau Ces impl mentations furent parfois tr s laborieuses et nous frein rent maintes fois dans l avancement du projet Et c t de a nous avons mis en application nos connaissances de l OpenGL pour pouvoir afficher de fa on correcte et agr able les r sultats que nous trouvions Tout le projet fut effectu en trin me il fut donc assez difficile d organiser nos avanc es Mais nous avons tout de m me r ussi partager les t ches et le travail pour en faire un projet quilibr selon les niveaux de chacun Enfin nous pouvons dire que ce projet fut tr s compliqu mettre en place et nous n avons malheureusement pas r ussi le terminer compl tement int grer toutes les fonctionnalit s demand es Certaines fonctions et algorithmes furent trop longs mettre en place pour pouvoir correctement finir le travail de plus notre projet fut sem d obstacles en tout genre qui ont allong le temps de travail Il serait int ressant de pouvoir terminer totalement le projet et le rendre encore plus captivant en finissant tout d abord les fonctionnalit s demand es puis en le rendant plus ludique en am liorant le graphisme de la carte en rajoutant des possibilit s ou peut tre m me un diteur de t
22. r A R alisation de l application interactive 1 Gestion souris Clavier Fonctionnement L interaction entre l utilisateur et le programme passe enti rement par la souris L utilisateur aura soit cliquer sur des boutons soit directement sur la carte elle m me A aucun moment il n aura besoin de passer par la console pour entrer une commande Ceci permet de simplifier grandement l utilisation de notre application et la rend disponible un plus large public Le clavier est quand lui pratiquement inutilis Seule la touche chap ou q permettent de quitter l application Impl mentation Il existe deux types v nements souris Celui g n r lorsqu on clic sur un bouton GLUI et celui g n r lorsqu on clic sur la carte Les clics sur la carte sont r cup r s par la fonction glut void mousel int button int state int x int y qui intercepte quel bouton a t cliqu et les coordonn es de la souris au moment du clic Ainsi en r cup rant les coordonn es du clic nous pouvons r cup rer dans le tableau de pixel de l image la valeur du pixel qui a t cliqu Une fois la valeur du pixel r cup r e nous pouvons d terminer s il s agit d un terrain vierge ou bien si la valeur du pixel est sup rieure 150 d une ville S il s agit d une ville on peut trouver simplement son indice en faisant une soustraction par 150 Une fois l indice r cup rer gr ce aux fonctions dont disposent les fichiers gares c et ville c no
23. ra un certain nombre d op rations sur le r seau Sa repr sentation virtuelle devra donc tre faite via une structure robuste que nous maitrisons parfaitement Le programme en disposant d un syst me d dition proposera de plus une utilisation au cas par cas Ainsi tout ce qui sera impl ment dans le programme devra fonctionner tous les coups A l impl mentation de chaque fonctionnalit il faudra ainsi prendre en compte tous les cas possibles et imaginables et essayer de programmer de fa on la plus g n rique possible Nous aurons de plus un certain nombre d algorithmes impl menter Si nous avons d j une id e de leur fonctionnement logique les mettre sous forme de code qui fonctionne semble tre une toute autre t che Enfin le programme propose une gestion graphique de l application Il faudra ainsi g rer en permanence les relations homme machine et retranscrire tout ce qui est demand par interface souris clavier affichage graphique la machine Il faudra aussi retranscrire de fa on agr able et compr hensible pour l utilisateur les donn es stock es par l ordinateur repr sentation du graphe des syst mes de rails etc UL Description et structuration du projet A Description globale du fonctionnement de l application Notre application est donc une application interactive qui propose plusieurs fonctionnalit s son utilisateur L affichage de l application se fait
24. rmes primitives telles que des cercles image h image c contient la structure image qui comprend sa largeur et sa hauteur la taille totale des pixels et le tableau de pixels Les fonctions permettent d crire ou lire une image au format ppm P5 de renvoyer la valeur d un pixel gr ce ses coordonn es de calculer la distance entre deux points algorithme de Bresenhami de d tecter la mer entre deux points ou bien encore de v rifier la coh rence des pixels de l image listeDouble h listeDouble c ces fichiers permettent de se servir de la structure de liste doublement cha n e que nous avons utilis e pour le graphe Ils comportent les fonctions classiques de parcours de liste placement en t te de liste etc Pour que cette structure de donn e soit facilement r utilisable nous avons d clar en void l objet que contient la liste Ainsi nous pouvons placer n importe quel type d objet dans notre liste sans avoir retoucher le code utils c utils h comporte divers fonctions de traitement des cha nes de caract res principalement utilis es lors de la lecture d image pour passer les commentaires point h structure permettant de repr senter un point 2D graphe h graphe c ces fichiers contiennent la structure de repr sentation de notre graphe ainsi que la majorit de nos algorithmes Ils seront d taill s dans la partie suivante de ce rapport main c c est le fichier principal de notre application C es
25. rs en profondeur et en largeur Il existe diff rentes fa ons de parcourir un graphe Les deux principales sont le parcours en profondeur et le parcours en largeur Nous avons donc impl ment ces deux parcours qui nous seront tr s utiles par la suite dans certains algorithmes Parcours en largeur Ce parcours consiste partir d un sommet S lister d abord tous ses voisins et puis ensuite les explorer un par un Il n cessite donc une file et aussi de pouvoir marquer les n uds par lesquels nous sommes d j pass s pour ne pas les compter plusieurs fois Pour la file nous avons utilis notre structure de liste doublement cha n qui comporte des fonctions permettant de l utiliser comme une file Pour le marquage nous avons ajout un champ visit notre structure gare ainsi on peut changer la valeur de ce flag et savoir que l on est d j pass par le n ud qui contient cette gare Voici le d roulement de l algorithme gt on ins re dans la file le sommet gt tant que la file n est pas vide gt On r cup re le premier l ment entr dans la file gt pour chacun de ses successeurs gt si le n ud n a pas d j t visit gt on le met dans la file gt et on le marque comme visit Cet algorithme est utilis par l algorithme qui permet de d tecter si de toutes gares on peut atteindre toute les autres Parcours en profondeur Ce parcours consiste pour chaque sommet prendre le premier voisin ju
26. s ensuite des structures impl ment es ainsi que des algorithmes qui les exploitent Ensuite nous nous consacrerons un chapitre sur l aspect interactif et graphique du projet durant lequel nous expliquerons son fonctionnement ainsi que la fa on dont nous l avons r alis e Nous finirons par exposer les r sultats de notre projet savoir quoi il ressemble et avec quelle efficacit tout ce que nous avons impl ment fonctionne 2 Sommaire A B La D B Positionnement dulprobl me sessions eseseniteeremnieitarrereeteanesetene des Ea eaaa 4 QUES ENIEUX EE 4 ge Ile EI A Description et structuration du projet iii 5 Description globale du fonctionnement de l application 5 Conception et structuration des fichiers ss 6 ege ET eat duu H StrUCtUratION eege E EE A A E An Pad en ee rm en ete emilie 7 Algorithmes snoin EEN EAR 8 1 Parcours en profondeur et en largeur ss 8 2 Changements d garei isissreissirumdiaiss EEN eege ee Sec 9 3 L algorithm de Br senh m 5 ARR Re tee ane Nees e 10 4 Plus court chemin entre deux gares 11 D PVC detre a tea le Rent MR ne dt dde tin tea fe aise lee 12 e Le 13 7 e ET Le rer nte met Re en nee die Aer lens de tennis 14 Application interactive et Guide de l Utilisateur 15 R alisation de l application interactive ss 15 Tl Gestion s uris Claviet issiria CAE RE AEN 15 KN nterne UA EE 15 3 DL 9 EL ET sirrinin
27. squ ce qu un sommet n ait plus de voisins et revient ensuite au sommet p re Ce parcours permet un parcours r cursif du graphe Ici aussi il est important de pouvoir marquer les n uds par lesquels nous sommes pass s pour viter de tourner ind finiment Voici le d roulement de l algorithme gt On marque le noeud gt tant qu il n est pas nul gt si il n est pas visit on rappel la fonction avec ce noeud gt on passe au successeur Cet algorithme est utilis dans plusieurs endroits du programme par exemple pour calculer le kilom trage total du graphe parcoursProfondeurKiloTotal ou bien encore pour compter le nombre de rails parcoursProfondeurNbRails 2 Changements de gare L algorithme de changements de gare consiste trouver partir d une ville donn e quelles villes sont accessibles en n changements Ainsi l utilisateur doit choisir une ville un certain nombre et verra appara tre sur la carte les villes o il peut se rendre L algorithme Cet algorithme utilise le parcours en largeur qui a t d crit ci dessus Il a donc fallut reprendre cet algorithme et changer quelques lignes pour l adapter notre cas Tout d abord il nous faut deux piles Elles permettront de garder les n uds que l on a visit s La premi re pile sert empiler les n uds que nous visitons tandis que la deuxi me contient les successeurs de ces derniers Au tout d but la fonction empile le premier n ud dans la pile F P
28. t cliqu par sa valeur et proc de gr ce un switch case au traitement correspondant GLUT_Rollout affichage new GLUI Rollout glui Afficher false rollout L outil de roll out permet de r duire ou afficher certains l ments de menu lorsque celui est trop charg comme dans notre programme GLUI_EditText creer nom de la ville nomVille Cet l ment est un champ texte dans lequel on peut rentrer du texte comme le nom d une ville que l on cr e et qui l ins re dans une variable string ici nomVille Tout de m me GLUI tant r alis avec du C nous avons du convertir chaque fois que n cessaire les strings envoy s par glui en char gr ce la commande char nomVille c_str qui caste le string en un char Ainsi en plus de la cr ation de GLUI il a fallu cr er une fonction qui r ceptionne tous les messages envoy s par les boutons de GLUI pour les traiter La cr ation de ce tout n a pas t la partie la plus complexe du projet mais elle a demand un certain temps de r flexion d exp rimentations et enfin d impl mentation 17 B Guide de l utilisateur Le guide de l utilisateur est destin expliquer un utilisateur lambda comment se servir du programme Tout ce qui est explication du fonctionnement de ces l ments a d j t fait dans la partie pr c dente Ici nous vous pr senterons les principales fonctionnalit s du logiciel et leur mode d emploi Dans
29. t ici que la partie openGL et l interface GLUI sont g r s UL Structures et Algorithmes A Structuration Notre application doit donc tre capable de g rer des connexions entre plusieurs villes et gares de r aliser des calculs sur les distances de trouver le plus court chemin entre deux gares en somme tout un ensemble de fonctionnalit s qui n cessitent une structuration robuste La structure la plus adapt e ces probl matiques est le graphe Nous avons donc du impl menter cette structure de donn es L impl mentation et les algorithmes qui utilisent le graphe sont dans les fichiers graphe c et graphe h tant donn qu il nous a t demand de pouvoir rajouter des n uds la vol e dans notre graphe nous avons donc opt pour une repr sentation par pointeur M me si celle ci est un peu plus complexe concevoir et manipuler qu une repr sentation FS APS elle a l avantage d tre plus souple car elle utilise un syst me de listes Gr ce la repr sentation par pointeur il nous est tr s facile de rajouter une gare notre graphe il suffit d ins rer un l ment en queue de liste gr ce la fonction appropri Si nous avions utilis une structure FS APS cela aurait tait beaucoup plus compliqu tant donn e qu il n est pas ais d agrandir un tableau Notre graphe se compose d une liste doublement cha n e de N uds Un N ud est une structure d finie dans graphe h qui contient un pointeur
30. t statiques les listes d roulantes etc Glui est ainsi une interface gratuite qui permet la cr ation simple d une interface qui pourra communiquer avec le programme via des boutons champs de texte etc Comment GLUI fonctionne GLUI fonctionne selon un principe simple A chaque l ment d interaction propos par glui est assign e une fonction qui va r cup rer le signal envoy par l l ment Ainsi lorsqu on clic sur un bouton celui ci va envoyer une fonction d termin e un signal et ce signal il suffit de lui faire correspondre l action d sir e Exemple pour afficher coucou dans une console il suffit d assigner le bouton glui une fonction dite de callback qui va r cup rer le message du bouton Cette fonction de callback va d terminer le bouton cliqu et lancer la commande d affichage de coucou dans la console Impl mentation Impl menter Glui n est pas tr s complexe Mais cela n cessite tout de m me certaines tapes qui peuvent prendre du temps surtout que GLUI est tr s peu document e on fonctionne beaucoup par t tonnements Il faut tout d abord cr er l lement glui et l affecter la fen tre glut correspondante GLUI glui GLUI Master create_glui GLUI glui gt set_main_gfx_window main window 16 Une fois ceci fait suffit d ajouter cet l ment glui ce que l on veut utiliser Ici nous avons utilis diff rents l ments GLUI S
31. table A la fin du calcul les villes r sultantes sont affich es en rouge S Mirky dadea gomteGare 8 d buet Comte MELECI HelmGare garadDurGare piinas Vrtttzare En rouge les gares accessibles en 1 changement depuis ComteGare 23 Le PVC permet de trouver le plus court trajet effectuer passant par plusieurs gares Dans notre programme nous devons s lectionner avec le clic droit au minimum trois gares puis l utilisateur actionne le bouton lan ant le PVC et alors le trajet obtenu s affiche en rouge tout comme pour le plus court chemin AdIrkuAgplEaee G omieGare ze 0 Les g 1440 E E A fs tier LONENE are garadDurGare PL nl 2 4 PT amine En rouge le chemin trouv par le pvc pour relier ComteGare HelmGare et MirkwoodGare 5 Le calcul du kilom trage total Le bouton GLUI calcul du kilom trage total permet de lancer le calcul des distances des rails Les distances s affichent imm diatement sur la carte au milieu de chaque rail Afficher Calcul du kilometrage total gomteGarezp1p 1440 e NarbadGare LONEME are e070 2 5 delmGare 1590 eee0 paradDurGare PLU pina Lugtbtzare 6 Gares auto accessibles L algorithme qui vise v rifier si le r seau est auto accessible n a pas de r sultat visible tr s marquant Il suffit d appeler la fonction l aide d une commande dans le menu pour voir s afficher si le r seau est auto accessible ou non Le graphe
32. taticText glui Console de message Il s agit d un l ment de texte simple Utilis pour pr senter g n ralement un autre outil il consiste afficher un libell sur l interface glui GLUI TextBox glui true 1 texthbox_cb Il s agit encore d un l ment de texte mais qui prend comme source de texte un l ment d fini de fa on externe Il est tr s utile de s en servir comme console de message par exemple Dans ce programme nous avons impl ment un l ment de texte global que l on modifie chaque fois que c est d sir Ainsi dans l interface Glui l affichage de cet l ment se modifie chaque modification Nous nous en sommes servi pour remplacer tout ce qui s affiche habituellement dans la console GLUI_Button glui Charger une region et ses villes 1 menu _glui Il s agit de l l ment principal de l interface D crivons son fonctionnement et les param tres qu il prend Le premier param tre correspond l l ment glui auquel on veut le rattacher ici la fen tre glui principale Le deuxi me correspond au libell affich sur le bouton Le troisi me correspond la valeur renvoy e par le bouton Le quatri me correspond la fonction appel e par le bouton Ces deux derniers param tres sont importants La fonction appel e par le bouton re oit la valeur envoy e par celui ci Chaque bouton doit en renvoyer une diff rente La fonction appel e d termine ainsi quel bouton es
33. ts taient co teux en temps et donc en argent les voyageurs de commercent qui travaillaient sur plusieurs villes cherchaient trouver le meilleur itin raire qui leur permettait de faire leur parcours en un temps optimal Ce probl me plut t simple lorsque peu de villes taient rejoindre se complexifie exponentiellement pour devenir tout simplement insoluble partir d un certain nombre de villes M me aujourd hui il est impossible pour un ordinateur en un temps raisonnable de calculer exactement le parcours optimal pour 20 villes on mettrait 1928 ans C est parce qu on ne peut trouver pour le moment une solution exacte que l on s est rabattu sur des algorithmes d approximation comme celui du PVC Comment fonctionne t il Le principe de fonctionnement du Probl me du voyageur de commerce est simple Il consiste dans un graphe partir d un des sommets que l on d sire relier puis de comparer les distances qui le s pare des ses successeur pour prendre la plus courte On se positionne ensuite sur le nouveau successeur et l on r applique ce successeur la m me chose Et ceci en faisant attention de ne pas passer deux fois par le m me chemin jusqu que tous les n uds que l on d sirait relier soient parcourus Impl mentation La premi re chose comme tout algorithme est de v rifier si les l ments pass s en param tre sont existants S il n y a qu une gare s lectionn e alors l
34. uis on empile dans la deuxi me pile Save tous les successeurs des n uds de F Une fois la pile F vid e on copie la pile Save dans F et l on recommence ainsi jusqu ce que la pile F ne contienne plus rien Cette m thode implique une double boucle while les deux ayant pour condition que la pile F ne soit pas vide Ceci diff re donc assez l g rement du parcours en largeur mais garde un principe similaire Vient ensuite la question des changements de gares Un compteur est initialis au d but de la fonction 1 A chaque passage dans la premi re boucle while le compteur est incr ment Puis une fois rendu dans la deuxi me boule while on teste si le compteur est gal nombre n rentr par l utilisateur Si tel est le cas les n uds sont non seulement empil s dans la pile Save mais galement ins r dans une liste Result C est cette liste qui sera retourn e en r sultat et qui contiendra toutes les gares recherch es L affichage Pour ce qui est de l affichage du r sultat nous avons repris les fonctions qui affichaient les villes et les gares Lors de l affichage des villes si la liste contenant le r sultat aux changements de gares contient quelque chose alors chaque ville affich e et contenue dans cette liste appara t d une couleur diff rente 3 L algorithme de Bresenham L algorithme L algorithme de Bresenham permet de d terminer quels sont les pixels qui doivent tre allum s afin de tracer une droite
35. us pouvons retrouver dans le graphe cette ville et ventuellement la gare qu elle contient Par la suite l action demand e par l utilisateur sera appel 2 Affichage du r seau L affichage de la carte et du r seau se fait gr ce aux fonctions de dessins d openGL Au niveau de la carte le programme dessine pour chaque pixel de l image de configuration un carr dont la couleur d pend de la valeur du pixel Les dimensions de ce carr dessin sont par d faut de 2 2 mais il est possible de changer facilement ces valeurs qui sont d clar es en variables globales de notre programme OpenGL nous permet simplement de dessiner un carr gr ce GL QUADS et aux coordonn es des 4 coins du carr En ce qui concerne les gares et les villes ils sont repr sent s respectivement par un cercle blanc et un carr noir Le cercle est trac gr ce une fonction que nous avons pr c demment d velopp e en TP de synth se d image Lorsque le graphe a t construit les coordonn es des villes et des gares ont t enregistr Ainsi pour afficher les gares et les villes il suffit de parcourir le graphe r cup rer la position et dessiner cet endroit l Nous avons aussi d cid d afficher le nom des gares et des villes Le principe est donc le m me on r cup re le nom de la ville ou de la gare et on l affiche la position de celle ci L affichage des rails est quant lui assez similaire Le programme effectue un parcours du graphe
36. vers une gare un entier pour enregistrer la distance et un pointeur vers le n ud successeur Le premier n ud de chaque cellule de la liste comporte l ensemble des gares du r seau ce sont les n uds principaux Et chacun de ces n uds pointent vers le n ud successeur du n ud principal c est dire un n ud au quel il est reli qui va pointer vers le second successeur du n ud principal ainsi de suite Gare de Lyon Gare Saint Charles Gare de Rouen LISTE DOUBLE QUI CONTIENT LES NOEUDS La construction du graphe au chargement du programme se d roule en deux tapes e Tout d abord gr ce au fichier de gares le programme va pour chaque gare instancier un objet gare l ins rer dans une structure de donn e N ud qui elle m me sera ins r e dans la liste qui va repr senter notre graphe Ainsi cette tape nous disposons de toutes les gares de notre r seau stock es dans notre liste e Ensuite gr ce au fichier de rails on va pouvoir construire les liaisons entre les gares et ainsi finir la construction de notre graphe Pour chaque ligne du fichier le programme r cup re les deux identifiants des gares Il va ensuite parcourir le graphe pour r cup rer des pointeurs vers ces deux gares Pour finir il va se positionner sur le n ud qui comprend la premi re gare et ajouter comme successeur un nouveau n ud qui contiendra le pointeur vers la seconde gare c est dire celle de destination B Algorithmes 1 Parcou
Download Pdf Manuals
Related Search