Calcul du chemin de moindre coût sur un raster de friction

Bonjour,

J’ai un raster de friction (les pixels contiennent des valeur du coût de leur traversée). Existe-t-il un algorithme connu qui permette de calculer le chemin de moindre coût entre deux points de ce raster, et par delà, le coût et la longueur de ce chemin ?

En gros c’est le problème du sauveteur sur la plage qui doit aller chercher le nageur, mais en version numérique plutôt qu’analytique.

Et accessoirement, cet algo est-il implémenté dans numpy ou une autre bibliothèque quelconque ?

Merci d’avance.

Salut,

Oui, sans plus de détails je pense que tu peux utiliser un algorithme de Dijkstra ou assimilé (A* ?) pour résoudre ton problème.

Par contre je ne pense pas que ce soit fourni de base avec numpy. Ça a l’air d’être fourni avec scipy.

Le problème c’est que l’algo de Dijkstra marche sur des données vectorielles, pas sur du matriciel où il y a une infinité de chemins possibles.

En continuant à chercher, j’ai effectivement trouvé des algo qui créent un graphe avec un nœud au centre de chaque pixel et des arrêtes entrent chaque pixels adjacents, et qui utilisent ensuite l’algo de Dijkstra. Le problème que je vois avec ce genre de méthode, c’est qu’elle force la trajectoire à traverser le centre des pixels traversés, et va donc systématiquement surestimer la distance finale.

Il n’existe pas des solutions au principe de Fermat avec des modèles types « éléments finis » ou n’importe quelle autre méthode où on discrétise un milieu hétérogène pour pouvoir obtenir une solution numérique ?

Attends, tu veux dire que tu as une carte divisée en sections (les pixels) qui ont chacun un coût de traversé et le problème est de trouver le meilleur chemin entre deux points? Si oui, ça ressemble à un plus court chemin euclidien.

Est-ce que tu as besoin d’une solution optimale, ou est-ce qu’une bonne solution (mais pas forcément la meilleur) est suffisante?

Tu peux regarder du côté de https://dl.acm.org/doi/10.1145/102782.102784, qui à l’air de parler exactement du problème que tu décris.

Si tu cherches plus une solution simple à implémenter pour avoir un résultat correcte, tu peux essayer de discrétiser ton milieu, par exemple en considérant N points dans chaque régions et en créant un graphe qui connecte chaque point à tous les points de la même région et des régions adjacentes (en utilisant la loi de Snell-Descartes pour calculer la distance). Tu peux ensuite optimiser ce chemin en optimisant la position des points d’intersections entre ton chemin et les frontières entre régions.

Edit: en y réfléchissant un peu plus, il serait plus intelligent de placer les points sur les frontières entre régions pour l’algo que je suggère. Des arêtes peuvent être ajoutés entre tous les points qui partagent une région.

Merci pour vous réponses :

Si oui, ça ressemble à un plus court chemin euclidien.

Oui, c’est à peu près ça. Si ce n’est que l’article Wikédia a l’air de parler de cellules binaire passe/passe-pas.

Est-ce que tu as besoin d’une solution optimale, ou est-ce qu’une bonne solution (mais pas forcément la meilleur) est suffisante?

Ben ça va dépendre. Idéalement j’aimerai bien une solution optimale. Mais bien évidement, si ça implique deux semaines de calculs dès que le raster dépasse le Mpx, la question de savoir ce que je veux ou pas risque de devenir secondaire.

Tu peux regarder du côté de https://dl.acm.org/doi/10.1145/102782.102784, qui à l’air de parler exactement du problème que tu décris.

Sacré article. Mais effectivement ça à l’air de parler de la problématique. Je garde ça sous le coude.

Si tu cherches plus une solution simple à implémenter pour avoir un résultat correcte, tu peux essayer de discrétiser ton milieu, par exemple en considérant N points dans chaque régions et en créant un graphe qui connecte chaque point à tous les points de la même région et des régions adjacentes (en utilisant la loi de Snell-Descartes pour calculer la distance). Tu peux ensuite optimiser ce chemin en optimisant la position des points d’intersections entre ton chemin et les frontières entre régions.

Ce que tu appels « N points », c’est les pixels ? Dans ce cas, ça revient à ce que j’ai décris plus haut non ? Avec l’algo de Dijkstra pluto que SD. D’ailleurs je ne vois pas trop comment appliquer SD sur un graphe.

Sinon, j’ai un peu cherché hier. Et en cherchant dans les publications d’optique plutôt que de SIG, j’ai trouvé le mot clé « équation eikonale ». Il semblerai que l’algo « canonique » de résolution numérique soit la Fast Marching Method. Si quelqu’un a des information sur cet algo, d’éventuels inconvénients, etc, je suis preneur.

j’ai trouvé un module python qui à l’air de faire le taf. Il est juste pas à jour avec la dernière version de numpy. Je vais tester ça.