line_iterator.h

/*
 * Software License Agreement (BSD License)
 *
 *  Copyright (c) 2010, Willow Garage, Inc.
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above
 *     copyright notice, this list of conditions and the following
 *     disclaimer in the documentation and/or other materials provided
 *     with the distribution.
 *   * Neither the name of Willow Garage, Inc. nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 */
 
#pragma once
 
#include "organized_index_iterator.h"
 
namespace pcl {
/**
 * \brief Organized Index Iterator for iterating over the "pixels" for a given line
 * using the Bresenham algorithm. Supports 4 and 8 neighborhood connectivity
 * \note iterator does not visit the given end-point (on purpose).
 * \author Suat Gedikli <gedikli@willowgarage.com>
 * \ingroup  geometry
 */
class LineIterator : public OrganizedIndexIterator {
public:
  /** \brief Neighborhood connectivity  */
  enum Neighborhood { Neighbor4 = 4, Neighbor8 = 8 };
 
public:
  /**
   * \brief Constructor
   * \param x_start column of the start pixel of the line
   * \param y_start row of the start pixel of the line
   * \param x_end column of the end pixel of the line
   * \param y_end row of the end pixel of the line
   * \param width width of the organized structure e.g. image/cloud/map etc..
   * \param neighborhood connectivity of the neighborhood
   */
  LineIterator(unsigned x_start,
               unsigned y_start,
               unsigned x_end,
               unsigned y_end,
               unsigned width,
               const Neighborhood& neighborhood = Neighbor8);
 
  /** \brief Destructor*/
  ~LineIterator() override;
 
  void
  operator++() override;
  unsigned
  getRowIndex() const override;
  unsigned
  getColumnIndex() const override;
  bool
  isValid() const override;
  void
  reset() override;
 
protected:
  /**
   * \brief initializes the variables for the Bresenham algorithm
   * \param[in] neighborhood connectivity to the neighborhood. Either 4 or 8
   */
  void
  init(const Neighborhood& neighborhood);
 
  /** \brief current column index*/
  unsigned x_;
 
  /** \brief current row index*/
  unsigned y_;
 
  /** \brief column index of first pixel/point*/
  unsigned x_start_;
 
  /** \brief row index of first pixel/point*/
  unsigned y_start_;
 
  /** \brief column index of end pixel/point*/
  unsigned x_end_;
 
  /** \brief row index of end pixel/point*/
  unsigned y_end_;
 
  // calculated values
  /** \brief current distance to the line*/
  int error_;
 
  /** \brief error threshold*/
  int error_max_;
 
  /** \brief increment of error (distance) value in case of an y-step (if dx > dy)*/
  int error_minus_;
 
  /** \brief increment of error (distance) value in case of just an x-step (if dx >
   * dy)*/
  int error_plus_;
 
  /** \brief increment of column index in case of just an x-step (if dx > dy)*/
  int x_plus_;
 
  /** \brief increment of row index in case of just an x-step (if dx > dy)*/
  int y_plus_;
 
  /** \brief increment of column index in case of just an y-step (if dx > dy)*/
  int x_minus_;
 
  /** \brief increment of row index in case of just an y-step (if dx > dy)*/
  int y_minus_;
 
  /** \brief increment pixel/point index in case of just an x-step (if dx > dy)*/
  int index_plus_;
 
  /** \brief increment pixel/point index in case of just an y-step (if dx > dy)*/
  int index_minus_;
};
 
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////////////////////////////////////////////
inline LineIterator::LineIterator(unsigned x_start,
                                  unsigned y_start,
                                  unsigned x_end,
                                  unsigned y_end,
                                  unsigned width,
                                  const Neighborhood& neighborhood)
: OrganizedIndexIterator(width)
, x_start_(x_start)
, y_start_(y_start)
, x_end_(x_end)
, y_end_(y_end)
{
  init(neighborhood);
}
 
////////////////////////////////////////////////////////////////////////////////
inline LineIterator::~LineIterator() = default;
 
////////////////////////////////////////////////////////////////////////////////
inline void
LineIterator::init(const Neighborhood& neighborhood)
{
  x_ = x_start_;
  y_ = y_start_;
  index_ = x_ * width_ + y_;
  error_ = 0;
 
  int delta_x = x_end_ - x_start_;
  int delta_y = y_end_ - y_start_;
 
  int x_dir = ((delta_x > 0) ? 1 : -1);
  int y_dir = ((delta_y > 0) ? 1 : -1);
 
  delta_x *= x_dir;
  delta_y *= y_dir;
 
  if (delta_x >= delta_y) {
    if (neighborhood == Neighbor4) {
      error_max_ = delta_x - delta_y;
      x_minus_ = 0;
      y_minus_ = y_dir;
      x_plus_ = x_dir;
      y_plus_ = 0;
 
      error_minus_ = -(delta_x * 2);
      error_plus_ = (delta_y * 2);
    }
    else {
      error_max_ = delta_x - (delta_y * 2);
      x_minus_ = x_dir;
      y_minus_ = y_dir;
      x_plus_ = x_dir;
      y_plus_ = 0;
 
      error_minus_ = (delta_y - delta_x) * 2;
      error_plus_ = (delta_y * 2);
    }
  }
  else {
    if (neighborhood == Neighbor4) {
      error_max_ = delta_y - delta_x;
      x_minus_ = x_dir;
      y_minus_ = 0;
      x_plus_ = 0;
      y_plus_ = y_dir;
 
      error_minus_ = -(delta_y * 2);
      error_plus_ = (delta_x * 2);
    }
    else {
      error_max_ = delta_y - (delta_x * 2);
      x_minus_ = x_dir;
      y_minus_ = y_dir;
      x_plus_ = 0;
      y_plus_ = y_dir;
 
      error_minus_ = (delta_x - delta_y) * 2;
      error_plus_ = (delta_x * 2);
    }
  }
 
  index_minus_ = x_minus_ + y_minus_ * width_;
  index_plus_ = x_plus_ + y_plus_ * width_;
}
 
////////////////////////////////////////////////////////////////////////////////
inline void
LineIterator::operator++()
{
  if (error_ >= error_max_) {
    x_ += x_minus_;
    y_ += y_minus_;
    error_ += error_minus_;
    index_ += index_minus_;
  }
  else {
    x_ += x_plus_;
    y_ += y_plus_;
    error_ += error_plus_;
    index_ += index_plus_;
  }
}
 
////////////////////////////////////////////////////////////////////////////////
inline unsigned
LineIterator::getRowIndex() const
{
  return y_;
}
 
////////////////////////////////////////////////////////////////////////////////
inline unsigned
LineIterator::getColumnIndex() const
{
  return x_;
}
 
////////////////////////////////////////////////////////////////////////////////
inline bool
LineIterator::isValid() const
{
  return (x_ != x_end_ || y_ != y_end_);
}
 
////////////////////////////////////////////////////////////////////////////////
inline void
LineIterator::reset()
{
  x_ = x_start_;
  y_ = y_start_;
  error_ = 0;
  index_ = x_ * width_ + y_;
}
 
} // namespace pcl