GeoExMachina

Blog géomatique

Tracé Graal (2)

AbracaDijkstra !!!

Suite du Tracé Graal, on continue sur les tracés automatiques de pistes ! Les avancées sont disponibles sur Github, dans le dépôt AutomaTracks.

Adapter un graphe à la création de tracé de route
Malgré mes tentatives de vouloir garder ça simple, ça ne l'est plus beaucoup. En effet le modèle de pistes automatiques que je souhaite réaliser devait respecter un certain nombre de contrainte : pente maximum en long, des coûts en fonction de la pente latérale (surcoût dû au terrassement nécessaire), et des contraintes de direction pour faire en sorte que les pistes soient praticables.

Le paramètre de contrainte de direction est celui qui a entrainé le plus de modification dans la création du graphe. Pour qu'un véhicule puisse progresser sans manoeuvre, il faut que le tracé des pistes respecte un certain rayon de courbure. Un rayon de courbure c'est le rayon du cercle tangeant à un point d'une courbe... vu qu'on travaille sur des polylignes, on a pas de courbe, mais le calcul peut se faire avec les médiatrices de deux lignes successives. Mais pour faire ce calcul il a fallu modifier la nature du graphe.

Auparavant, chaque pixel du MNT était un noeud et ces derniers étaient reliés par des liaisons. Maintenant, un noeud c'est un segment entre deux pixel généré par la méthode de l'article précédent. Pour chaque pixel, on créé 8, 24, 40, 48 noeuds selon le paramètre choisi, et au passage on ne crée pas les noeuds dont la pente excède la pente maximale souhaitée. Chacun de ces noeuds contient l'identifiant du pixel d'où il part et celui du pixel où il va. Ainsi, pour chaque noeud (nd1) on va connaître le pixel d'arrivé et l'on va pouvoir tester la contrainte de direction avec les noeuds (nd2) qui partent de ce même pixel. S'il respecte la contrainte de direction (par défaut j'utilise 20m de rayon de courbure pour un MNT à 5m de résolution), alors on ajoute le noeud (nd2) en liaison au premier noeud (nd1).


Le rayon de courbure varie selon l'azimuth des deux segments


Pour finir, lors de la création de chaque noeud on calcule aussi le coût théorique pour passer du pixel de départ au pixel d'arrivé. La fonction de coût dépend de la pente latérale. A partir de cette pente, on peut calculer l'ampleur du terrassement à faire sur ce segment, c'est le coût considéré dans AutomaTracks.

Déterminer le chemin de moindre coût
Il existe des heuristiques permettant de trouver des solutions de chemin réalisables. Cependant, s'il s'agit de trouver LE chemin de moindre coût entre deux noeuds d'un graphe, il n'existe pas trente-six solutions, il nous faut l'algorithme de Dijkstra.

Celui-ci va partir d'un noeud et il va se propager au fur et à mesure dans le graphe, en retenant le coût le moins élevé pour accéder à chacun des noeuds. Il n'y a pas d'illustration plus parlante que celle-la :



Dans notre cas, chaque noeud a un coût comme attribut, ainsi qu'un coût cumulé qui sert lors de la recherche du chemin. Au début du traitement on initialise le cout cumulé du noeud de départ. Alors l'algorithme calcule le coût d'accès aux noeuds avec lesquels il a une liaison et dont le coût cumulé sera égal au coût cumulé précédent, plus son propre coût. L'algorithme poursuit sa route ainsi jusqu'à tomber sur le noeud d'arrivé.

Utilisation dans AutomaTracks et correction de tracé
Pour nos besoins en Guyane, on a besoin de suivre au maximum les lignes de crêtes afin d'éviter les zones hydromorphes. Par conséquent le réseau de points à relier est issu des polylignes de crêtes. On extrait les pics et les cols remarquables (des points de passages obligés) de ces polylignes, ainsi que les points de départ et d'arrivé de chaque polyligne, afin de garder la cohérence du réseau. Tous nos points ont alors un attribut de ligne L_id et un attribut de point P_id au sein de la ligne. Il est également possible de créer soi-même son réseau de point du moment que les attributs de la couche de points sont respectés.



AutomaTracks va alors réaliser les chemins de moindre coût entre chaque paire de points qui se suivent, en gardant également la cohérence de direction entre deux tracés. Pour cela, il réalise des clips du MNT autour de la zone de calcul. Lors du tracé d'un nouveau chemin de moindre coût, il fera démarrer la propagation du graphe du point de départ, mais aussi depuis les chemins précédemment calculés. Si tel est le cas, AutomaTracks corrige les polylignes concernées pour éviter de laisser des petits morceaux sans cohérence.