Vous disposez de données décrivant les routes du 13e arrondissement de Paris.
On souhaite se donner un point de départ, un point d'arrivée et calculer un plus court chemin respectant les routes indiquées dans les fichiers.
Bien qu'on se soit limité au 13e arrondissement, les données sont volumineuses : plus de 10 000 nœuds et autant d'arêtes entre ces nœuds.
Vous disposez de deux fichiers.
paris13.nodes.csv Résumé
| id | lat | lng |
|---|---|---|
| 0 | 48.8263456 | 2.3614982 |
| 1 | 48.826185 | 2.3572626 |
| 2 | 48.8260749 | 2.3552177 |
| 3 | 48.8258123 | 2.3503781 |
| 4 | 48.8257548 | 2.3465866 |
Ce fichier donne des nœuds correspondant à des points sur la carte. Cette nœud sont identifié par un entier id.
paris13.edges.csv Résumé
| source | dest | longueur | type | vmax | deuxsens | nom |
|---|---|---|---|---|---|---|
| 83 | 6609 | 6.27 | tertiary | 30 | 0 | Rue Nationale |
| 6609 | 4033 | 3.62 | tertiary | 30 | 0 | Rue Nationale |
| 4033 | 6611 | 5.72 | tertiary | 30 | 0 | Rue Nationale |
| 6611 | 2460 | 4.5 | tertiary | 30 | 0 | Rue Nationale |
| 10231 | 21 | 18.69 | secondary | 30 | 0 | Avenue des Gobelins |
Il s'agit de routes.
source et dest correspondent à id dans l'autre fichier.deuxsens = 1 quand la voie est à double sens, 0 pour un sens unique.Il faudra
Les fichiers que je donne sont réduits et simplifiés par exemple aux gros fichiers que l'on pourrait télécharger sur openstreetmap c'est d'ailleurs là que j'ai pris mes données. Vous ne pourrez donc pas indiquer les points de départ et d'arrivée comme vous le feriez sur une application comme GoogleMap. Une solution est de préciser une localisation GPS et de choisir le nœud le plus proche.
Pour cela, vous pouvez utiliser le calcul de distance en mètres entre deux points de latitude et longitude connues (en degrés):
$$distance = 111\,120 \cdot \sqrt{\left[(lng_1 - lng_2)\cdot\cos\left(\frac{lat_1 + lat_2}{360}\cdot\pi\right) \right]^2 + \left[lat_1 - lat_2\right]^2}$$