Fast marching example for Grid

[Shervin Javdani]

An example of the fast marching method, applied to calculating the distance on a grid (see fig 11 of Sethian). The zero position is on the top left corner, and we're trying to find the distance to any other node (where distance between two connected nodes is d). If d=1, and distance to the node diagonally across is 1 + 1/sqrt(2) (as shown).

Also, it's not hard to see that if you ran the fast marching method, any node would only depend on the node to the left and above. So on the bottom right, you see how you can calculate the value of the new node given these two.

In the attached code, it iterates through and solves this for an arbitrary d (iterates diagonally down, and solves for the one row and one column. So it's not quite the fast marching method!). It continues until you get to the point (x,y) = (1,1). So the true distance should be sqrt(2). You can try playing with d and see it gets closer to this value as d -> 0.

-Shervin and JP