n-Dimensional Fast Methods  0.7
 All Classes Functions Variables Typedefs Pages
FMM< grid_t, heap_t > Class Template Reference

Implements the Fast Marching Method (FMM). More...

#include <fmm.hpp>

Inheritance diagram for FMM< grid_t, heap_t >:
Collaboration diagram for FMM< grid_t, heap_t >:

Public Member Functions

 FMM (HeurStrategy h=NOHEUR)
 
 FMM (const char *name, HeurStrategy h=NOHEUR)
 
virtual void setup ()
 Executes EikonalSolver setup and sets maximum size for the narrow band.
 
virtual void computeInternal ()
 Actual method that implements FMM.
 
void setHeuristics (HeurStrategy h)
 Set heuristics flag. True is activated. It will precompute distances if not done already.
 
HeurStrategy getHeuristics () const
 Returns heuristics flag.
 
virtual void clear ()
 Clears the solver, it is not recommended to be used out of the destructor.
 
virtual void reset ()
 Clears temporal data, so it is ready to run again.
 
virtual void precomputeDistances ()
 Computes euclidean distance between goal and rest of cells.
 
virtual double getPrecomputedDistance (const unsigned int idx)
 Extracts the euclidean distance calculated from precomputeDistances function distance between two positions.
 
virtual void printRunInfo () const
 
- Public Member Functions inherited from EikonalSolver< grid_t >
 EikonalSolver (const std::string &name)
 
virtual double solveEikonal (const int &idx)
 Solves nD Eikonal equation for cell idx. If heuristics are activated, it will add the estimated travel time to goal with current velocity. More...
 
- Public Member Functions inherited from Solver< grid_t >
 Solver (const std::string &name)
 
virtual void setEnvironment (grid_t *g)
 Sets and cleans the grid in which operations will be performed.
 
virtual void setInitialAndGoalPoints (const std::vector< unsigned int > &init_points, unsigned int goal_idx)
 Sets the initial and goal points by the indices of the grid.
 
virtual void setInitialPoints (const std::vector< unsigned int > &init_points)
 Sets the initial points by the indices of the grid.
 
virtual void setInitialAndGoalPoints (const std::array< unsigned int, grid_t::getNDims()> &init_coord, const std::array< unsigned int, grid_t::getNDims()> &goal_coord)
 Sets the initial and goal points by the coordinates of the grid.
 
virtual void setInitialPoints (const std::array< unsigned int, grid_t::getNDims()> &init_coord)
 Sets the initial point by the coordinates of the grid.
 
void compute ()
 Computes the distances map. Will call setup() if not done already.
 
template<class T >
T * as ()
 Cast this instance to a desired type.
 
template<class T >
const T * as () const
 Cast this instance to a desired type.
 
const std::string & getName () const
 Returns name of the solver.
 
grid_t * getGrid () const
 Returns a pointer to the grid used.
 
virtual double getTime () const
 

Private Attributes

heap_t narrow_band_
 Instance of the heap used.
 
HeurStrategy heurStrategy_
 Flag to activate heuristics and corresponding strategy.
 
std::vector< double > distances_
 Stores the precomputed heuristic distances.
 
bool precomputed_
 Flag to indicate if distances_ is already computed.
 
std::array< unsigned int,
grid_t::getNDims()> 
heur_coord_
 Goal coord, goal of the second wave propagation (actually the initial point of the path).
 

Additional Inherited Members

- Protected Member Functions inherited from EikonalSolver< grid_t >
double solveEikonalNDims (unsigned int idx, unsigned int dim)
 Solves the Eikonal equation assuming that Tvalues_ is sorted.
 
- Protected Member Functions inherited from Solver< grid_t >
int sanityChecks ()
 Performs different check before a solver can proceed.
 
- Protected Attributes inherited from EikonalSolver< grid_t >
std::vector< double > Tvalues_
 Auxiliar vector with values T0,T1...Tn-1 variables in the Discretized Eikonal Equation.
 
std::array< unsigned int,
2 *grid_t::getNDims()> 
neighbors_
 Auxiliar array which stores the neighbor of each iteration of the computeFM() function.
 
- Protected Attributes inherited from Solver< grid_t >
grid_t * grid_
 Grid container.
 
std::string name_
 Solver name.
 
bool setup_
 Setup status.
 
std::vector< unsigned int > init_points_
 Initial index.
 
unsigned int goal_idx_
 Goal index.
 
std::chrono::time_point
< std::chrono::steady_clock > 
start_
 Time measurement variables.
 
std::chrono::time_point
< std::chrono::steady_clock > 
end_
 
double time_
 Time elapsed by the compute method.
 

Detailed Description

template<class grid_t, class heap_t = FMDaryHeap<FMCell>>
class FMM< grid_t, heap_t >

It uses as a main container the nDGridMap class. The nDGridMap type T has to be an FMCell or something inherited from it.

The grid is assumed to be squared, that is Delta(x) = Delta(y) = leafsize_

The type of the heap introduced is very important for the behaviour of the algorithm. The following heaps are provided:

  • FMDaryHeap wrap for the Boost D_ary heap (generalization of binary heaps). Set by default if no other heap is specified. The arity has been set to 2 (binary heap) since it has been tested to be the more efficient in this algorithm.
  • FMFibHeap wrap for the Boost Fibonacci heap.
  • FMPriorityQueue wrap to the std::PriorityQueue class. This heap implies the implementation of the Simplified FMM (SFMM) method, done automatically because of the FMPriorityQueue::increase implementation.
External documentation:
FMM: A. Valero, J.V. Gómez, S. Garrido and L. Moreno, The Path to Efficiency: Fast Marching Method for Safer, More Efficient Mobile Robot Trajectories, IEEE Robotics and Automation Magazine, Vol. 20, No. 4, 2013. DOI: 10.1109/MRA.2013.2248309>
[PDF]

SFMM: M.W. Jones, J.A. Baerentzen, M. Sramek, 3D Distance Fields: A Survey of Techniques and Applications, IEEE Transactions on Visualization and Computer Graphics, Vol. 12, No. 4, 2006. DOI <a href=http://dx.doi.org/10.1109/TVCG.2006.56">110.1109/TVCG.2006.56</a><br> <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1634323">[PDF]

Copyright (C) 2014 Javier V. Gomez www.javiervgomez.com

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition at line 64 of file fmm.hpp.

Constructor & Destructor Documentation

template<class grid_t, class heap_t = FMDaryHeap<FMCell>>
FMM< grid_t, heap_t >::FMM ( HeurStrategy  h = NOHEUR)
inline
Todo:
automate the naming depending on the heap.

Definition at line 67 of file fmm.hpp.


The documentation for this class was generated from the following file: