Discussion :

[Rumpel]

Bonjour,

Je voudrais comprendre en profondeur cet algorithme.
Je connais bien Dijkstra pour l'avoir déjà implémenté, mais là les différences entre les 2 algos me semblent flous ...
A priori FMM permet de résoudre des problèmes continus.
Par exemple si j'ai le fameux problème du secouriste qui doit courir sur la plage (forcément il nage trois moins vite qu'il ne court) quelle sera sa trajectoire ?
Est ce qu'on peut résoudre ce problème de façon exacte, c'est à dire sans avoir une solution en "escalier" ? (en utilisant l'algo, évidement en utilisant des équations issues de l'optique on y arrive aussi ...)

[kolodz]

Si tu met en équation ton problème tu a juste à trouver le minimum de la fonction. Ce qui devrait être un problème de seconde.

Donc la problématique, c'est de le mettre en équation !
L'équation de base étant :

Durée = Veau * Distance(eau)+ Vterre * Distance(terre)

Il faut juste remplacer :

Distance(eau)
Distance(terre)

Par quelque chose qui est en fonction du point O. Si on note O' le point de projection de A perpendiculaire à l'eau.
On a le triangle rectangle AO'O et on a :

AO² =AO'²+OO'²

Et pour B

OB²=OB'²+B'B²

Sachant que AO'² et B'B² sont des constantes dans notre problème seule OO'² et OB'² varie.
Si tu exprime ces distances en fonction d'une même variable. Tu pourra avoir la solution exacte au problème.

Après, la mise en équation et la résolution tu trouvera probablement (pas sûr) la correspondance suivant :

En tout cas, ce la match deux cas limites :

1. AOB est aligné et donc les angles sont nuls.
2. la vitesse sur la plage est de très loin supérieur à la vitesse dans l'eau et i est maximal et r null.

Mais, il faudrait poser les équations pour vérifier !

Cordialement,
Patrick Kolodziejczyk.

source :
http://en.wikipedia.org/wiki/Refraction