Bresenham.hh

/*
This file is part of the BIAS library (Basic ImageAlgorithmS).

Copyright (C) 2003-2009    (see file CONTACT for details)
  Multimediale Systeme der Informationsverarbeitung
  Institut fuer Informatik
  Christian-Albrechts-Universitaet Kiel


BIAS is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

BIAS 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 Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License
along with BIAS; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/


#ifndef __Bresenham_hh__
#define __Bresenham_hh__

#include <bias_config.h>


#include <Base/ImageUtils/EightWaySymmetry.hh>


namespace BIAS{
  /** @class Bresenham
    * @brief Scans a line using Bresenhams integer arithmetic algorithm.
    *  Either Init() or the according constructor have to be called befor GetNext().
    *  @author Felix Woelk
    *  @ingroup g_image_other
    */
  class Bresenham {
  public:
    inline Bresenham();

    inline Bresenham(const int start[2], const int end[2]);

    inline Bresenham(const unsigned int start[2], const unsigned int end[2]);

    inline Bresenham(const double start[2], const double end[2]);

    inline ~Bresenham();

    inline void Init(const int start[2], const int end[2]);

    inline void Init(const unsigned int start[2], const unsigned int end[2])
    { Init((int *)start, (int *)end); };

    inline void Init(const double start[2], const double end[2]);

    inline bool GetNext(int next[2]);

    inline bool GetNext(unsigned int next[2])
    { return GetNext((int *)next); };

    inline bool GetNext(double next[2]);

  protected:
    EightWaySymmetry<int> _iSym;

    enum TLineType _eLineType;

    int _iStart[2];
    int _iEnd[2];
    int _iTransformedCurrent[2];
    int _iTransformedStart[2];
    int _iTransformedEnd[2];
    int _iDx;
    int _iDy;
    double _dDx;
    double _dDy;
    long int _iEps;
#ifdef BIAS_DEBUG
    bool _bInitialized;
#endif
  };




  Bresenham::Bresenham()
  {
#ifdef BIAS_DEBUG
    _bInitialized=false;
#endif
  }

  Bresenham::~Bresenham()
  {}

  Bresenham::Bresenham(const int start[2], const int end[2])
  {
    Init(start, end);
#ifdef BIAS_DEBUG
    _bInitialized=true;
#endif
  }

  Bresenham::Bresenham(const unsigned int start[2], const unsigned int end[2])
  {
    Init(start, end);
#ifdef BIAS_DEBUG
    _bInitialized=true;
#endif
  }

  Bresenham::Bresenham(const double start[2], const double end[2])
  {
    Init(start, end);
#ifdef BIAS_DEBUG
    _bInitialized=true;
#endif
  }

  void Bresenham::Init(const int start[2], const int end[2])
  {
    _iStart[0]=start[0];
    _iStart[1]=start[1];
    _iEnd[0]=end[0];
    _iEnd[1]=end[1];
    _eLineType=_iSym.DetermineLineType(start[0], start[1], end[0], end[1]);
    _iSym.Transform(_eLineType, _iStart, _iTransformedStart);
    _iSym.Transform(_eLineType, _iEnd, _iTransformedEnd);
    _iSym.Transform(_eLineType, _iStart, _iTransformedCurrent);
    _iDx = _iTransformedEnd[0] - _iTransformedStart[0];
    _iDy = _iTransformedEnd[1] - _iTransformedStart[1];
    // let GetNext return the starting point first
    _iEps = -_iDy;
    _iTransformedCurrent[0]--;
    _dDx = _dDy = 0.0;
#ifdef BIAS_DEBUG
    _bInitialized=true;
#endif
  }

  void Bresenham::Init(const double start[2], const double end[2])
  {
    // fixes uninitialized usage warning, compiler does not notice
    // that this gets ultimately initialized via call-by-reference
    double transfstart[2] = { 0.0, 0.0 };
    EightWaySymmetry<double> dSym;

    _iStart[0]=(int)rint(start[0]);
    _iStart[1]=(int)rint(start[1]);
    _iEnd[0]=(int)rint(end[0]);
    _iEnd[1]=(int)rint(end[1]);

    _eLineType=_iSym.DetermineLineType(_iStart[0], _iStart[1], _iEnd[0],
                                       _iEnd[1]);
   /* std::cerr <<"start: ("<<start[0]<<", "<<start[1]<<")  end :("
              <<end[0]<<", "<<end[1]<<")  line type: "<<_eLineType<<std::endl;*/
    _iSym.Transform(_eLineType, _iStart, _iTransformedStart);
    _iSym.Transform(_eLineType, _iEnd, _iTransformedEnd);
    _iSym.Transform(_eLineType, _iStart, _iTransformedCurrent);
    _iDx = _iTransformedEnd[0] - _iTransformedStart[0];
    _iDy = _iTransformedEnd[1] - _iTransformedStart[1];
    dSym.Transform(_eLineType, start, transfstart);

    _dDx=(double)_iTransformedStart[0]-transfstart[0];
    _dDy=(double)_iTransformedStart[1]-transfstart[1];
    _iEps = (int)rint(((double)(_iDy)*_dDx)+((double)(_iDy)*_dDy));
    // let GetNext return the starting point first
    _iEps -= _iDy;
    _iTransformedCurrent[0]--;
   /* std::cerr <<"_iStart: (" <<_iStart[0]<<", "<<_iStart[1]
              <<")  transfstart: ("<<transfstart[0]<<", "<<transfstart[1]
              <<")  _iDx: "<<_iDx<<"  _iDy: "<<_iDy
              <<"  _dDx: "<<_dDx<<"  _dDy: "<<_dDy<<"   _iEps: "<<_iEps<<std::endl;*/

#ifdef BIAS_DEBUG
    _bInitialized=true;
#endif
  }

  bool Bresenham::GetNext(int next[2])
  {
#ifdef BIAS_DEBUG
    if (!_bInitialized){
      BIASERR("call Init befor GetNext");
      BIASABORT;
    }
#endif
    bool result=true;
    _iTransformedCurrent[0]++;
    _iEps += _iDy;
    if ((_iEps << 1) >= _iDx){
      _iTransformedCurrent[1]++;
      _iEps -= _iDx;
    }
    if (_iTransformedCurrent[0]>_iTransformedEnd[0] ||
        _iTransformedCurrent[1]>_iTransformedEnd[1]){
#ifdef BIAS_DEBUG
      _bInitialized=false;
#endif
      result=false;
    } else {
      _iSym.InverseTransform(_eLineType, _iTransformedCurrent, next);
      result=true;
    }
    return result;
  }

  bool Bresenham::GetNext(double next[2])
  {
    bool result;
    int inext[2];
    result = GetNext(inext);
    next[0]=(double)inext[0] + _dDx;
    next[1]=(double)inext[1] + _dDy;

    return result;
  }

} // namespace


#endif // __Bresenham_hh__