Henry's ShortestPathComparison investigates applying Kimmel and Sethian's Fast Marching Method to computing shortest paths on terrain. Their original paper can assign a speed to each point in the plane, but does not make this speed dependent on direction -- the set of possible velocities that can be assigned at a point are isotropic. For terrain, we would like speed in the projection plane to depend on the Euclidean distance being traversed on the terrain, or on other anisotropic velocity assignments (e.g., slow uphill, fast downhill.)

Suppose that our terrain is represented by the graph of z(x,y), which is the surface f(x,y) = (x,y, z(x,y)).

The distance traveled in the projection depends on the gradient

The tangent plane approximation at x,y is given by the gradient

If we wanted to assign velocities in the projection, based on Euclidean distance traversed on the terrain, we could use the gradient at x,y.

I should do this in detail, but for now, I'm just going to fix Henry's page for an approximation to the simple case. -- JackSnoeyink - 23 May 2005

Henry's old text:

Suppose that adjacent elevation points a and b are 20 feet apart on the projection and have an elevation difference of 10 feet. The Euclidian distance between them is around 22.36 feet. We thus let the front speed at the intermediate grid points be 22.36/20: the ratio of the Euclidian distance to the projected distance. We could also let the front speed be a function of this ratio. The function we use determines the weight we give to changes in elevation.

Adjacent elevation points are a fixed distance apart; this distance is known as the cell spacing. We can find the elevation at grid points between adjacent elevation points through linear interpolation.

We will call horizontal or vertical lines that connect elevation points elevation lines. To find the front speed at grid points that are not collinear with two neighboring grid points we must do the following. We first draw horizontal and vertical lines through the grid point. Each of these lines is parallel to a line that connects two adjacent elevation points and is the same length as this line. We get the change in elevation along the horizontal and vertical lines that we have drawn. We use this information to find the Euclidian length of both the horizontal and the vertical line. We then take the ratio of each line's Euclidian distance to its projected distance, which gives us the horizontal speed and the vertical speed at the point. We combine these horizontal and vertical speeds in a velocity vector and find the length of the vector to get the speed of the front at the grid point.