Fast marching method

From Wikipedia, the free encyclopedia

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

F(x)|\nabla T(x)|=1.

Typically, such a problem describes the evolution of a closed curve as a function of time T with speed F(x) in the normal direction at a point x on the curve. The speed function is specified, and the time at which the contour crosses a point x is obtained by solving the equation.

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:

F(x)|\nabla _{S}T(x)|=1,\,\,{\mbox{for the surface}}\,\,S,\,{\mbox{and}}\,\,x\in S.

was introduced by Ron Kimmel and Sethian.

  • Maze as speed function shortest path

  • Distance map multi-stencils with random source points

See also

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.