n-Dimensional Fast Methods Documentation

These pages provide basic documentation about the Fast Methods library.

• Software design
• Building and installing
• Benchmarking
• nDGridMap implementation: Probably, the most complex part of the code. It encapsulates the complexity of the n-dimensional generalization, so that solvers are implemented almost independently of the number of dimensions.

Note

Some of the classes are just wrappers that can be used with lower level classes. For instance, declaring a SFMM<nDGridMap<FMCell,2>> is the same as using FMM<nDGridMap<FMCell,2>, FMPriorityQueue<FMCell>>. The same happens with the *(Star) solvers.

Due to the nDimensional implementation, the Eikonal solver code for a given index is probably not very optimized, since it computes from 1D to nD until a better solution is not possible. For 2D and 3D (and probably nD) this is not necessary, but my tests while implementing FSM obligated me to do it that way in order to have consistent results.

ALGORITHMS

All the theory and algorithms implemented in this library can be found in my PhD thesis. In fact, all the benchmarking data in chapter 4 has been produced with this library and it is stored on the experiments branch.

Fast Marching Methods:

• FMM: Fast Marching Method with Binary Queue and Fibonacci Queue (binary by default).
• FMM*: FMM with CostToGo heuristics.
• SFMM: Simplified Fast Marhching Method.
• SFMM*: SFMM with CostToGo heuristics..

O(n) Fast Marching Methods:

• GMM: Group Marching Method.
• UFMM: Untidy Fast Marching Method.
• FIM: Fast Iterative Method.

Fast Sweeping Methods:

• FSM: Fast Sweeping Method.
• LSM: Lock Sweeping Method.
• DDQM: Dynamic Double Queue Method.

Fast Marching Square motion planning algorithms:

• FM2: Fast Marching Square Method.
• FM2*: Fast Marching Square Star FM2 with CostToGo heuristics.

Authors

• Javier V. Gomez javvgomez at gmail.com
• Jose Pardeiro jose.pardeiro at gmail.com
• Pablo Gely