BresenhamCircle.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 __BresenhamCircle_hh__
#define __BresenhamCircle_hh__
#include "bias_config.h"

namespace BIAS {

  /** @brief Scans a circle using Bresenham's integer arithmetic algorithm.
   *
   *  - Either Init() or the according constructor have to be called before
   *    GetNext()
   *  - Points on circle are not given in continous manner, i.e. subsequent
   *    calls to GetNext() return (x,y), (y,x), (x,-y), (y,-x),
   *    (-x,-y), (-y,-x), (-x,y), (-y,x)
   *  - Fast
   *  @ingroup g_image_other
   *  @author fw, clean-up + refactoring by rwulff 02/2010
   */
  class BresenhamCircle {

  public:

    /**
     * @brief Default constructor. You have to call Init() by yourself before
     *        calling GetNext().
     */
    inline BresenhamCircle() {
    }


    /**
     * @brief Constructor.
     *
     * @param center
     *        the center for this BresenhamCircle
     *
     * @param radius
     *        the radius for this BresenhamCircle
     */
    inline BresenhamCircle(int center[2], int radius) {
      Init(center, radius);
    }

    /**
     * @brief Destructor.
     */
    inline ~BresenhamCircle() {
    }


    /**
     * @brief Initialises this BresenhamCircle with new center and radius.
     *
     * @param center
     *        the new center for this BresenhamCircle
     *
     * @param radius
     *        the new radius for this BresenhamCircle
     */
    inline void Init(int center[2], int radius) {
      center_[0] = center[0];
      center_[1] = center[1];
      radius_    = radius;

      current_[0] = 0;
      current_[1] = radius_;

      d_       = 1 - radius_;
      deltaE_  = 3;
      deltaSE_ = -2 * radius_+5;

      // let GetNext return the starting point first
      current_[0]--;
      if (d_ >= 0) {
        current_[1]++;
      }
      count_ = 0;

#ifdef BIAS_DEBUG
      initialized_ = true;
#endif
    }


    /**
     * @brief Returns the coordinate of the next point on the circle.
     *
     * Can be called in a while loop:
     *
     * int nextCoords[2];
     * while (bresCirc.GetNext(nextCoords)){
     *   // draw nextCoords in image
     * }
     *
     * @param next
     *        the returned coordinate of the next point on the circle
     *
     * @return true if there are still points left on the circle or
     *         false if the circle is finished
     */
    inline bool GetNext(int next[2]) {
#ifdef BIAS_DEBUG
    if (!initialized_)
      BIASERR("call Init() before GetNext()");
#endif

    bool result=true;

    if (count_ == 0){
      if (current_[1] > current_[0]){
        if (d_ < 0){
          d_ += deltaE_;
          deltaE_ += 2;
          deltaSE_ += 2;
        } else {
          d_ += deltaSE_;
          deltaE_ += 2;
          deltaSE_ += 4;
          current_[1]--;
        }
        current_[0]++;
        next[0] = current_[0] + center_[0];
        next[1] = current_[1] + center_[1];
        count_ = 1;
      }
    } else {
      next[0] = center_[0];
      next[1] = center_[1];

      switch (count_){
      case 1:
        next[0] += current_[1];
        next[1] += current_[0];
        break;
      case 2:
        next[0] += current_[0];
        next[1] -= current_[1];
        break;
      case 3:
        next[0] += current_[1];
        next[1] -= current_[0];
        break;
      case 4:
        next[0] -= current_[0];
        next[1] -= current_[1];
        break;
      case 5:
        next[0] -= current_[1];
        next[1] -= current_[0];
        break;
      case 6:
        next[0] -= current_[0];
        next[1] += current_[1];
        break;
      case 7:
        next[0] -= current_[1];
        next[1] += current_[0];
        break;
      }

      count_++;
      if (count_ == 8) {
        count_=0;
      }

      if (count_ == 0 && current_[1] <= current_[0]) {
#ifdef BIAS_DEBUG
        initialized_ = false;
#endif
        result = false;
      }
    }
    return result;
  }


  protected:

    int center_[2]; // center coo
    int radius_;
    int current_[2];
    int d_;
    int deltaE_;
    int deltaSE_;
    int count_;

#ifdef BIAS_DEBUG
    bool initialized_;
#endif
  };

} // namespace

#endif // __BresenhamCircle_hh__