An Object Finite Element Library

FastMarching2D.h

Go to the documentation of this file.

/*==============================================================================

                                    O  F  E  L  I

                           Object  Finite  Element  Library

  ==============================================================================

   Copyright (C) 1998 - 2008 Rachid Touzani

   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; Version 2 of the License.

   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, write to the :

   Free Software Foundation
   Inc., 59 Temple Place - Suite 330
   Boston, MA  02111-1307, USA

  ==============================================================================

               Definition of Template Class FastMarching2D for Fast Marching
                     algorithm on 2-D structured uniform grids

  ==============================================================================*/


#ifndef __FAST_MARCHING_2D_H
#define __FAST_MARCHING_2D_H

#include <stdlib.h>
#include <math.h>

#include <valarray>
using std::valarray;

#include "OFELI_Config.h"
#include "Vect.h"
#include "Point2D.h"
#include "Grid.h"

namespace OFELI {

#ifndef DOXYGEN_SHOULD_SKIP_THIS
struct Pt
{
   size_t ix, iy;
   double val;
   Pt & operator=(double a) { ix = iy = 0; val = a; return *this; }
};
#endif /* DOXYGEN_SHOULD_SKIP_THIS */

#ifndef DOXYGEN_SHOULD_SKIP_THIS
struct ErrorInFastMarching2D {
   void Message(const char *file, size_t line, int code);
};
#endif /* DOXYGEN_SHOULD_SKIP_THIS */


class FastMarching2D
{
 public:

    FastMarching2D();

    FastMarching2D(const Grid &g, Vect<double> &ls);

    FastMarching2D(const Grid &g, Vect<double> &ls, Vect<double> &F);

    ~FastMarching2D();

    void execute();

    void Check();

 private:
    bool _ext;
    size_t _nx, _ny;
    int _bw, _current;
    double _hx, _hy;
    Grid _g;
    const Grid *_cg;
    Vect<size_t> _pos;
    Vect<double> *_A, *_v;
    Vect<double> _ls, _f, _u, _sol;
    Vect<Pt> _heap;
    ErrorInFastMarching2D _e;

    void Init();

//  Function defining obstacle
    double Obstacle(Point2D<double> a);

//  Return distance between point x and the segment joining point y to z.
    double Dist(const Point2D<double> &x, const Point2D<double> &y, const Point2D<double> &z);

//  Add an element to the heap and reorganize it
    void Add(double Uij, size_t a, size_t b);

//  Modify an element of the heap
    void Modify(double Uij, size_t a, size_t b);

//  Delete the first element in the heap that has the minimal value
    Pt Delete();

//  Return the positive solution of a second degree equation
    inline double PositiveSol(double a, double b, double c)
    {
       double delta = b*b - 4*a*c;
       if (delta == 0)
          return(-0.5*b/a);
       else {
          if (delta < 0) {
             cerr << "Error in FastMarching2D: No positive solution found." << endl;
             exit(1);
          }
          else
             return (0.5*(sqrt(delta)-b)/a);
       }
    }

//  Distance between selected points and the boundary
    void ExtendLocalVelocity(Vect<double> &dis);

    void Int(size_t k, size_t l, Vect<double> &a, Point2D<double> &x1, Point2D<double> &x2);

//  Interpolate a function on a segment
    double Interp(Point2D<double> &xx);

//  Set to 'gray' the neighbors of (i,j)
    void setGray(size_t i, size_t j);
    void setGrayWithObstacle(size_t i, size_t j);
};

} /* namespace OFELI */

#endif

Copyright © 1998-2007 Rachid Touzani