↑ arvau

Wikipedia / Fast marching method

The fast marching method is a numerical method created by James Sethian for solving boundary value problems of the Eikonal equation:

. The fast marching method takes advantage of this optimal control interpretation of the problem in order to build a solution outwards starting from the "known information", i.e. the boundary values.

The algorithm is similar to Dijkstra's algorithm and uses the fact that information only flows outward from the seeding area. This problem is a special case of level-set methods. More general algorithms exist but are normally slower.

Extensions to non-flat (triangulated) domains solving

, were introduced by Ron Kimmel and James Sethian.

Algorithm

.

The algorithm works just like Dijkstra's algorithm but differs in how the nodes' values are calculated. In Dijkstra's algorithm, a node's value is calculated using a single one of the neighboring nodes. However, in solving the PDE of the neighboring nodes are used.

Nodes are labeled as far (not yet visited), considered (visited and value tentatively assigned), and accepted (visited and value permanently assigned).

  1. and label them as far as accepted.

  2. , use the Eikonal update formula as considered.

  3. as accepted.

  4. .

  5. was labeled as far, update the label to considered.

  6. If there exists a considered node, return to step 3. Otherwise, terminate.

See also

Notes