Ce que demande vraiment un graphe de sentiers construit sur OpenStreetMap

Demandez à WayMaker une boucle de 10 km à l'ombre près de Meeks Bay et il en trace une en quelques secondes, profil d'altitude et répartition par type de surface comprise. Toutes ces boucles ne survivent pas au contact du terrain. Le graphe a déjà routé à travers une barrière fermée depuis des années par un district forestier ou un propriétaire privé, parce que rien dans les données ne l'avait jamais dit. C'est pour combler ce manque que le graphe de sentiers doit être construit.

Le propos, énoncé assez franchement pour qu'un sceptique puisse s'y accrocher : le routage sur sentiers est d'abord un problème de filtrage des données. Un moteur comme GraphHopper, ce sont les 20 % faciles du travail. Les 80 % restants consistent à réduire OpenStreetMap aux chemins qu'un randonneur peut parcourir légalement, à donner à ces chemins une altitude honnête, et à refuser de faire confiance à ceux qui mentent. WayMaker expose un point d'API dédié au graphe de sentiers (waymaker.guide) à cause de ces 80 %, pas malgré eux.

Filtrer sur les tags qui décident si un randonneur rentre chez lui

La géométrie d'OpenStreetMap est presque toujours juste sur l'endroit où passe un sentier. La difficulté se loge dans ce que les tags disent de cette géométrie, parce que les tags qui comptent pour un randonneur sont ceux qu'un routeur automobile ignore allègrement.

Quatre groupes portent l'essentiel du poids. surface sépare l'asphalte de la terre, du sol, de l'herbe et de la roche, ce qui décide de vos chaussures et de ce que vos chevilles doivent anticiper. sac_scale note le caractère alpin sur l'échelle T1 à T6 du Club alpin suisse : T1 est un chemin familial, plat, évident, tandis que T5 et au-delà signalent un terrain où une glissade a des conséquences. trail_visibility va d'excellent jusqu'à rien, et la distance entre bon et mauvais sépare le suivi d'un corridor balisé de la navigation d'après une trace GPX. tracktype note les pistes non revêtues, d'un grade1 nivelé et praticable en citadine jusqu'à quelque chose qui ressemble à peine à une route au grade5.

La première version de notre filtre conservait tout highway=track, sur une théorie qui sonnait bien : les pistes forment les connecteurs légaux vers la plupart des départs de sentiers. Le routeur s'est alors mis à envoyer des gens en chaussures de running sur des pistes forestières, certaines semées de blocs rocheux, d'autres barrées d'un panneau d'interdiction d'entrée. Les pistes passent maintenant par la même porte que tous les autres chemins, et smoothness arbitre souvent quand surface et tracktype sont en désaccord. Une règle plus discrète tirée de la même leçon : un tag absent ne doit jamais passer pour un tag favorable. Une absence de données n'est pas une présence de qualité.

Voici la forme de la requête Overpass qui récupère les chemins candidats pour une région (boîte englobante en degrés décimaux, un secteur de départ de randonnée en exemple) :

[out:json][timeout:90];
(
  way["highway"~"^(path|footway|steps|pedestrian|track)%%CODEBLOCK_0%%quot;]
     ["foot"!~"^(no|private)%%CODEBLOCK_0%%quot;]
     ["access"!~"^(no|private)%%CODEBLOCK_0%%quot;]
     (39.05,-120.20,39.15,-119.95);
);
out tags geometry;

La plupart des chemins passent. C'est dans les échecs que vit l'ingénierie.

Écarter les voies motorisées sans couper les sentiers qui les traversent

Réduisez les résultats de la requête aux chemins praticables à pied, et le piège suivant est déjà armé. OpenStreetMap scinde les voies là où elles se croisent, si bien qu'un sentier qui traverse une piste forestière partage avec elle le nœud du croisement. Les deux mauvaises réponses sont disponibles ici, et nous avons produit les deux à un moment ou à un autre.

Supprimez les voies motorisées en même temps que leurs nœuds, et vous supprimez des nœuds que des sentiers survivants référencent encore, ce qui laisse des trous sur lesquels un routeur s'étouffe, ou dont il émerge avec une ligne droite qu'il n'a aucune légitimité de tracer. L'ordre praticable est l'inverse : supprimer les voies seules, garder tout nœud qu'une voie survivante référence, et auditer ce qui subsiste. L'audit en apprend plus que la suppression. Comptez les composantes connexes du graphe survivant et inspectez les grandes coupures. Une région qui devrait former un seul réseau et qui revient en morceaux, c'est généralement un connecteur classé à tort comme motorisé.

Le conflit de fond, en dessous de tout cela : la classe de véhicule et la légalité piétonne sont deux questions différentes, et OpenStreetMap répond aux deux. Une route peut être fermée aux voitures tout l'été et ouverte aux bottes, et les derniers 200 mètres de beaucoup d'accès aux départs de sentiers sont exactement cela : une highway=service taguée pour des véhicules agricoles ou forestiers, qu'un filtre fondé sur « est-ce une route ? » ampute. Filtrez sur l'accès à pied, jamais sur la classe de véhicule.

L'altitude vient d'un autre fichier planet

OpenStreetMap enregistre rarement la hauteur le long d'une voie, donc le graphe doit aller chercher sa troisième dimension ailleurs. Open-Elevation sert du terrain issu de SRTM, la mission radar de navette spatiale diffusée à une maille d'environ 30 m au sol. WayMaker échantillonne la géométrie de chaque voie survivante à pas fixe d'environ 25 m, arrondit chaque échantillon vers une clé de cache et passe les requêtes par lots, si bien qu'une région se réchauffe une fois et reste chaude.

L'altitude n'est pas de la décoration. Les distances qu'un randonneur marche réellement sont des longueurs 3D, et sur terrain pentu l'écart avec la longueur à plat se compte en quelques pour cent, davantage sur les montées en lacets serrés. Le cumul de dénivelé positif et négatif, le chiffre que tout traileur cite, n'existe pas sans elle. Et le modèle de coût du routeur en a besoin : un graphe planaire croit que gagner 300 mètres de dénivelé sur un kilomètre coûte pareil qu'un kilomètre plat, et voilà comment un routeur aveugle à la pente finit par recommander un mur à quelqu'un en chaussures de trail.

Nous avons fait l'ordre à l'envers et ne le referions pas. Le routeur a tourné la plupart des premiers mois de WayMaker sur des longueurs planaires avant que l'altitude ne rejoigne le graphe, ce qui veut dire que chaque chiffre de dénivelé cumulé de cette époque était une approximation en terre plate, présentée en toute confiance. Joignez l'altitude au graphe dès la construction, du premier commit.

Les voies qui mentent

Certaines lignes sur la carte sont de la fiction. Une voie qui traverse un talus à découvert avec trail_visibility=no vous dit la vérité : vous naviguerez, vous ne marcherez pas. La même ligne sans aucun tag de visibilité du tout, et une réalité en pointillés sous les pieds, c'est un mensonge que le graphe hérite en bloc. Les fermetures sont des menteuses plus discrètes : une saison d'orages et de ravinements laisse une voie verte sur la carte pendant des années, les fermetures saisonnières sont parfois taguées et souvent pas, et les tags d'accès contredisent les panneaux des propriétaires dans les deux sens. Nous avons trouvé les pires cas de la manière honnête : quelqu'un a marché l'itinéraire et nous a écrit.

La direction est un piège silencieux à part entière. Les tags à sens unique sur les descentes de VTT s'appliquent aux vélos, tandis qu'un randonneur qui monte est en général en règle, et souvent c'est tout l'objet de la montée. La direction doit se gérer par type d'activité, pas comme une propriété de la voie elle-même. Un graphe qui stocke un seul drapeau de direction par voie se plante pour précisément les deux activités qui partagent le plus de sentiers.

Une voie filtrée, jointe à l'altitude, ressort façonnée ainsi :

{
  "id": 102938475,
  "tags": {
    "highway": "path",
    "name": "Rim Trail",
    "surface": "dirt",
    "trail_visibility": "good",
    "sac_scale": "hiking"
  },
  "node_ids": [47101, 47102, 47108],
  "elevation_m": [1912.4, 1913.1, 1915.9],
  "length_3d_m": 50.2,
  "gain_m": 3.5,
  "oneway": { "hiking": false, "mtb": true }
}

Cet objet oneway est toute l'histoire de la direction compressée dans un champ, et le routeur le lit différemment selon ce que vous lui avez demandé.

Ce que le graphe ne peut toujours pas savoir

Trois limites que nous énonçons désormais à découvert, parce que les utilisateurs méritent les petites lignes.

La couverture est inégale précisément là où la randonnée l'est. Le réseau de sentiers est dense là où les randonneurs sont denses. Au fond des campagnes, de vrais sentiers ne sont pas cartographiés, et des sentiers cartographiés existent que personne n'a parcouru avec une trace GPS depuis des années. Nous n'interpolons pas : si le graphe n'a pas de connecteur, l'itinéraire s'arrête ou fait un détour, et un vide honnête vaut mieux qu'une ligne inventée.

L'attribution est une obligation, pas une courtoisie. WayMaker est construit sur OpenStreetMap, sur le terrain SRTM d'Open-Elevation, sur GraphHopper, Overpass, et sur les tuiles OpenTopoMap et OpenFreeMap, crédités dans l'application. Parce que le graphe de sentiers est une base de données dérivée des données OSM, les termes share-alike de l'ODbL la suivent. Quiconque construit sur un tel graphe hérite lui aussi de la mention, et le traiter comme un problème de pied de page ne survit pas au contact d'un avocat.

La péremption est un problème de confiance. Un itinéraire sur un pont emporté vaut pire qu'un message d'erreur, parce que l'utilisateur n'a aucun moyen de savoir que la ligne est morte l'hiver dernier. La fraîcheur dans OSM est une fonction des contributeurs, et les contributeurs se répartissent à peu près aussi inégalement que les sentiers. Le correctif partiel passe par un chemin de signalement dans l'application, avec des corrections renvoyées vers OSM quand une modification profite à chaque carte qui la lit. L'énoncé honnête, c'est que ce correctif est partiel.

Ce qu'on emporte

Budgétez les semaines dans les proportions du travail réel. La plupart partent dans les filtres, les audits de connectivité, les jointures d'altitude et le traitement des signalements. Quelques-unes au routeur, qui n'a jamais dû être la partie dure. Puis dépensez un après-midi à marcher deux boucles que vous pouvez vérifier en personne, parce que le seul benchmark qui compte, c'est de savoir si le graphe est juste là où se trouvent les bottes de quelqu'un.

Un routeur n'est honnête qu'à la mesure des voies qu'on a gardées.