top of page

Plus court chemin pour aller d'un point à un autre.

Nous avions commencé à travailler avec des points colorés affichés par Open Street Map.

Nous nous sommes rendu compte après des mois d'essais que ce n'était pas pratique et peu lisible.

C'est pourquoi nous voulons, à partir d'une position de départ et d'arrivée, déterminer le meilleur chemin en fonction de la pollution et de la distance

Nous avons utilisé programme « A »  qui nous permet de trouver rapidement le plus court chemin dans une matrice de donnée. L’algorithme prend des valeurs et les transforme en nœuds que nous pouvons par la suite afficher à l’aide d’un graphe. Suite à cela, le code a été amélioré avec l’ajout du module « turtle » utilisé en Python pour tracer des arêtes. Dans ce nouvel algorithme, les valeurs prises par "turtle" étaient des valeurs que nous avons fixées et donc pas représentatives de la réalité. Les valeurs ci-dessus ont été choisies arbitrairement, si on les compare aux valeurs réelles :

Capture d’écran 2021-02-14 à 15.20.20.
Capture d’écran 2021-02-14 à 15.24.08.
Capture d’écran 2021-02-14 à 15.20.31.

•Nous avons ensuite « parser » c'est-à-dire comment passer d’une méthode d’écriture (OSM) à une autre (XML) ; ce dernier étant supporté par Python, et ainsi nous permettant de faire un graphe.

Pour cela il faut passer par « Element Tree » associé chaque latitude, longitude et iD à un unique nœud et si ce nœud possède une interaction avec d’autres (route, piste cyclable, etc.) et donc les relier ensemble.

• Le seul problème avec ce système c’est que nous ne pouvons que modéliser une zone réduite de la ville (car si l’on prend la carte de Massy en entier elle est trop lourde pour l’algorithme) et que le parsing et le traçage du graph même à partir d’une carte assez petite reste assez longue. Nous y travaillons, à ce jour nous avons  réussi à réduire le parsing à environ 2.2s.

Le problème de la taille du fichier reste cependant un problème pas encore résolu…  

bottom of page