Itinéraire: méthodes utilisées pour stocker des cartes routières sur ordinateur et quelques algorithmes simples pour identifier les chemins

Résumé du document

La première étape a été l'analyse des solutions existantes concernant l'affichage de cartes géographiques et le calcul d'itinéraire.
Une fois cette étape terminée, est venu le temps de l'analyse des spécifications fonctionnelles. Cette phase est essentielle dans la réalisation d'une application.
En effet, c'est elle qui va définir les “verrous”, faire émerger un schéma de conception (dans notre cas un diagramme UML) et permettre de répartir les tâches de la manière la plus optimale possible.
L'application devant être réalisée en Java, nous avons dû choisir entre la version 1.6 et la nouvelle version Java 1.7. Notre choix s'est porté sur Java 1.6 pour des raisons de facilité, en effet, les premiers tests effectués en Java 1.7 ne nous ont pas paru concluant, et comme nous n'étions pas sûrs des versions disponibles sur les ordinateurs de l'UM2 nous avons fait notre développement en Java 1.6.

Extraits

[...] B. C. D. E. VI. A. B. C D. E. VII. [...]

[...] Grâce au schéma, nous pouvons voir que la position de y maximum est facile à définir. En effet, le clic doit être situé au-dessus du segment AC, or la position en de C est égale à celle de A donc il n'y a pas de calcul à faire Concernant le calcul de la position en minimal, nous avons remarqué que le triangle représentant le panneau était symétrique. En effet, ABC étant un triangle isocèle en la hauteur issue de B constitue un axe de symétrie. [...]

[...] Nous avons juste modifié l'algorithme pour qu'il trace les points sans s'occuper de leur type. Le tracé était donc devenu assez simple : Pour chaque route Pour chaque point i de la route du second au dernier Tracer une arrête entre le point i-1 et le point i Enregistrer cette arête dans la liste des arêtes Fin pour Fin pour L'enregistrement de l'arête permet d'avoir des fonctionnalités plus poussées au niveau de l'interface homme-machine. Nous développerons cette partie ultérieurement dans le rapport. [...]

[...] La distance est connue grâce à l'addition des distances entre chaque étape. L'algorithme commence par une initialisation qui recherche les différents antécédents de chaque point. Par la suite, tant que la condition d'arrêt n'est pas remplie, on cherche un arc qui raccourcisse le chemin. S'il n'en existe pas ou si la distance à la racine est négative, la condition d'arrêt est remplie. Sinon, on modifie l'antécédent de y par la valeur du sommet qui raccourcit le chemin. On modifie la distance et on ajuste l'arbre pour qu'il reste cohérent. [...]

[...] Si la distance entre la racine (le point de départ de notre itinéraire) et le sommet (appelons le est plus courte en passant par un autre sommet (appelons le alors le père de Y est le sommet X. Le tableau d'entiers était le plus facile à utiliser car il est léger et permet un accès rapide à l'information. L'algorithme utilise aussi une liste de voisins pour sélectionner les points Y. En effet, ce serai une perte de temps de parcourir tous les sommets s'il faut faire un test pour savoir si le sommet Y est un voisin du sommet X. [...]