Basic Image AlgorithmS Library 2.8.0

Bresenham.hh

00001 /*
00002 This file is part of the BIAS library (Basic ImageAlgorithmS).
00003 
00004 Copyright (C) 2003-2009    (see file CONTACT for details)
00005   Multimediale Systeme der Informationsverarbeitung
00006   Institut fuer Informatik
00007   Christian-Albrechts-Universitaet Kiel
00008 
00009 
00010 BIAS is free software; you can redistribute it and/or modify
00011 it under the terms of the GNU Lesser General Public License as published by
00012 the Free Software Foundation; either version 2.1 of the License, or
00013 (at your option) any later version.
00014 
00015 BIAS is distributed in the hope that it will be useful,
00016 but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 GNU Lesser General Public License for more details.
00019 
00020 You should have received a copy of the GNU Lesser General Public License
00021 along with BIAS; if not, write to the Free Software
00022 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00023 */
00024 
00025 
00026 #ifndef __Bresenham_hh__
00027 #define __Bresenham_hh__
00028 
00029 #include <bias_config.h>
00030 
00031 
00032 #include <Base/ImageUtils/EightWaySymmetry.hh>
00033 
00034 
00035 namespace BIAS{
00036   /** @class Bresenham
00037     * @brief Scans a line using Bresenhams integer arithmetic algorithm.
00038     *  Either Init() or the according constructor have to be called befor GetNext().
00039     *  @author Felix Woelk
00040     *  @ingroup g_image_other
00041     */
00042   class Bresenham {
00043   public:
00044     inline Bresenham();
00045 
00046     inline Bresenham(const int start[2], const int end[2]);
00047 
00048     inline Bresenham(const unsigned int start[2], const unsigned int end[2]);
00049 
00050     inline Bresenham(const double start[2], const double end[2]);
00051 
00052     inline ~Bresenham();
00053 
00054     inline void Init(const int start[2], const int end[2]);
00055 
00056     inline void Init(const unsigned int start[2], const unsigned int end[2])
00057     { Init((int *)start, (int *)end); };
00058 
00059     inline void Init(const double start[2], const double end[2]);
00060 
00061     inline bool GetNext(int next[2]);
00062 
00063     inline bool GetNext(unsigned int next[2])
00064     { return GetNext((int *)next); };
00065 
00066     inline bool GetNext(double next[2]);
00067 
00068   protected:
00069     EightWaySymmetry<int> _iSym;
00070 
00071     enum TLineType _eLineType;
00072 
00073     int _iStart[2];
00074     int _iEnd[2];
00075     int _iTransformedCurrent[2];
00076     int _iTransformedStart[2];
00077     int _iTransformedEnd[2];
00078     int _iDx;
00079     int _iDy;
00080     double _dDx;
00081     double _dDy;
00082     long int _iEps;
00083 #ifdef BIAS_DEBUG
00084     bool _bInitialized;
00085 #endif
00086   };
00087 
00088 
00089 
00090 
00091   Bresenham::Bresenham()
00092   {
00093 #ifdef BIAS_DEBUG
00094     _bInitialized=false;
00095 #endif
00096   }
00097 
00098   Bresenham::~Bresenham()
00099   {}
00100 
00101   Bresenham::Bresenham(const int start[2], const int end[2])
00102   {
00103     Init(start, end);
00104 #ifdef BIAS_DEBUG
00105     _bInitialized=true;
00106 #endif
00107   }
00108 
00109   Bresenham::Bresenham(const unsigned int start[2], const unsigned int end[2])
00110   {
00111     Init(start, end);
00112 #ifdef BIAS_DEBUG
00113     _bInitialized=true;
00114 #endif
00115   }
00116 
00117   Bresenham::Bresenham(const double start[2], const double end[2])
00118   {
00119     Init(start, end);
00120 #ifdef BIAS_DEBUG
00121     _bInitialized=true;
00122 #endif
00123   }
00124 
00125   void Bresenham::Init(const int start[2], const int end[2])
00126   {
00127     _iStart[0]=start[0];
00128     _iStart[1]=start[1];
00129     _iEnd[0]=end[0];
00130     _iEnd[1]=end[1];
00131     _eLineType=_iSym.DetermineLineType(start[0], start[1], end[0], end[1]);
00132     _iSym.Transform(_eLineType, _iStart, _iTransformedStart);
00133     _iSym.Transform(_eLineType, _iEnd, _iTransformedEnd);
00134     _iSym.Transform(_eLineType, _iStart, _iTransformedCurrent);
00135     _iDx = _iTransformedEnd[0] - _iTransformedStart[0];
00136     _iDy = _iTransformedEnd[1] - _iTransformedStart[1];
00137     // let GetNext return the starting point first
00138     _iEps = -_iDy;
00139     _iTransformedCurrent[0]--;
00140     _dDx = _dDy = 0.0;
00141 #ifdef BIAS_DEBUG
00142     _bInitialized=true;
00143 #endif
00144   }
00145 
00146   void Bresenham::Init(const double start[2], const double end[2])
00147   {
00148     // fixes uninitialized usage warning, compiler does not notice
00149     // that this gets ultimately initialized via call-by-reference
00150     double transfstart[2] = { 0.0, 0.0 };
00151     EightWaySymmetry<double> dSym;
00152 
00153     _iStart[0]=(int)rint(start[0]);
00154     _iStart[1]=(int)rint(start[1]);
00155     _iEnd[0]=(int)rint(end[0]);
00156     _iEnd[1]=(int)rint(end[1]);
00157 
00158     _eLineType=_iSym.DetermineLineType(_iStart[0], _iStart[1], _iEnd[0],
00159                                        _iEnd[1]);
00160    /* std::cerr <<"start: ("<<start[0]<<", "<<start[1]<<")  end :("
00161               <<end[0]<<", "<<end[1]<<")  line type: "<<_eLineType<<std::endl;*/
00162     _iSym.Transform(_eLineType, _iStart, _iTransformedStart);
00163     _iSym.Transform(_eLineType, _iEnd, _iTransformedEnd);
00164     _iSym.Transform(_eLineType, _iStart, _iTransformedCurrent);
00165     _iDx = _iTransformedEnd[0] - _iTransformedStart[0];
00166     _iDy = _iTransformedEnd[1] - _iTransformedStart[1];
00167     dSym.Transform(_eLineType, start, transfstart);
00168 
00169     _dDx=(double)_iTransformedStart[0]-transfstart[0];
00170     _dDy=(double)_iTransformedStart[1]-transfstart[1];
00171     _iEps = (int)rint(((double)(_iDy)*_dDx)+((double)(_iDy)*_dDy));
00172     // let GetNext return the starting point first
00173     _iEps -= _iDy;
00174     _iTransformedCurrent[0]--;
00175    /* std::cerr <<"_iStart: (" <<_iStart[0]<<", "<<_iStart[1]
00176               <<")  transfstart: ("<<transfstart[0]<<", "<<transfstart[1]
00177               <<")  _iDx: "<<_iDx<<"  _iDy: "<<_iDy
00178               <<"  _dDx: "<<_dDx<<"  _dDy: "<<_dDy<<"   _iEps: "<<_iEps<<std::endl;*/
00179 
00180 #ifdef BIAS_DEBUG
00181     _bInitialized=true;
00182 #endif
00183   }
00184 
00185   bool Bresenham::GetNext(int next[2])
00186   {
00187 #ifdef BIAS_DEBUG
00188     if (!_bInitialized){
00189       BIASERR("call Init befor GetNext");
00190       BIASABORT;
00191     }
00192 #endif
00193     bool result=true;
00194     _iTransformedCurrent[0]++;
00195     _iEps += _iDy;
00196     if ((_iEps << 1) >= _iDx){
00197       _iTransformedCurrent[1]++;
00198       _iEps -= _iDx;
00199     }
00200     if (_iTransformedCurrent[0]>_iTransformedEnd[0] ||
00201         _iTransformedCurrent[1]>_iTransformedEnd[1]){
00202 #ifdef BIAS_DEBUG
00203       _bInitialized=false;
00204 #endif
00205       result=false;
00206     } else {
00207       _iSym.InverseTransform(_eLineType, _iTransformedCurrent, next);
00208       result=true;
00209     }
00210     return result;
00211   }
00212 
00213   bool Bresenham::GetNext(double next[2])
00214   {
00215     bool result;
00216     int inext[2];
00217     result = GetNext(inext);
00218     next[0]=(double)inext[0] + _dDx;
00219     next[1]=(double)inext[1] + _dDy;
00220 
00221     return result;
00222   }
00223 
00224 } // namespace
00225 
00226 
00227 #endif // __Bresenham_hh__
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends