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.
*
*/
#ifndef __PCL_LINE_ITERATOR__
#define __PCL_LINE_ITERATOR__
#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 */
typedef enum {Neighbor4 = 4, Neighbor8 = 8} Neighborhood;
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*/
virtual ~LineIterator ();
virtual void operator ++ ();
virtual unsigned getRowIndex () const;
virtual unsigned getColumnIndex () const;
virtual bool isValid () const;
virtual void reset ();
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 ()
{
}
////////////////////////////////////////////////////////////////////////////////
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
#endif // __PCL_LINE_ITERATOR__
pcl::LineIterator::Neighbor4
Definition: line_iterator.h:52
pcl::OrganizedIndexIterator::index_
unsigned index_
the index of the current pixel/point
Definition: organized_index_iterator.h:96
pcl::LineIterator::operator++
virtual void operator++()
go to next pixel/point in image/cloud
Definition: line_iterator.h:224
pcl::LineIterator::index_plus_
int index_plus_
increment pixel/point index in case of just an x-step (if dx > dy)
Definition: line_iterator.h:122
pcl
Definition: convolution.h:45
pcl::LineIterator::~LineIterator
virtual ~LineIterator()
Destructor.
Definition: line_iterator.h:145
pcl::LineIterator::Neighborhood
Neighborhood
Neighborhood connectivity.
Definition: line_iterator.h:52
pcl::LineIterator::getRowIndex
virtual unsigned getRowIndex() const
returns the row index (y-coordinate) of the current pixel/point
Definition: line_iterator.h:244
pcl::LineIterator::index_minus_
int index_minus_
increment pixel/point index in case of just an y-step (if dx > dy)
Definition: line_iterator.h:125
pcl::LineIterator::y_plus_
int y_plus_
increment of row index in case of just an x-step (if dx > dy)
Definition: line_iterator.h:113
pcl::LineIterator::y_start_
unsigned y_start_
row index of first pixel/point
Definition: line_iterator.h:88
pcl::LineIterator::reset
virtual void reset()
resets the iterator to the beginning of the line
Definition: line_iterator.h:265
pcl::LineIterator::init
void init(const Neighborhood &neighborhood)
initializes the variables for the Bresenham algorithm
Definition: line_iterator.h:151
pcl::LineIterator::y_minus_
int y_minus_
increment of row index in case of just an y-step (if dx > dy)
Definition: line_iterator.h:119
pcl::LineIterator::x_end_
unsigned x_end_
column index of end pixel/point
Definition: line_iterator.h:91
pcl::LineIterator::x_start_
unsigned x_start_
column index of first pixel/point
Definition: line_iterator.h:85
pcl::LineIterator
Organized Index Iterator for iterating over the "pixels" for a given line using the Bresenham algorit...
Definition: line_iterator.h:48
pcl::LineIterator::LineIterator
LineIterator(unsigned x_start, unsigned y_start, unsigned x_end, unsigned y_end, unsigned width, const Neighborhood &neighborhood=Neighbor8)
Constructor.
Definition: line_iterator.h:134
pcl::LineIterator::Neighbor8
Definition: line_iterator.h:52
pcl::OrganizedIndexIterator
base class for iterators on 2-dimensional maps like images/organized clouds etc.
Definition: organized_index_iterator.h:45
pcl::LineIterator::x_
unsigned x_
current column index
Definition: line_iterator.h:79
pcl::LineIterator::isValid
virtual bool isValid() const
return whether the current visited pixel/point is valid or not.
Definition: line_iterator.h:258
pcl::LineIterator::x_minus_
int x_minus_
increment of column index in case of just an y-step (if dx > dy)
Definition: line_iterator.h:116
pcl::LineIterator::y_end_
unsigned y_end_
row index of end pixel/point
Definition: line_iterator.h:94
pcl::LineIterator::error_minus_
int error_minus_
increment of error (distance) value in case of an y-step (if dx > dy)
Definition: line_iterator.h:104
pcl::LineIterator::x_plus_
int x_plus_
increment of column index in case of just an x-step (if dx > dy)
Definition: line_iterator.h:110
pcl::OrganizedIndexIterator::width_
unsigned width_
the width of the image/cloud
Definition: organized_index_iterator.h:93
pcl::LineIterator::error_max_
int error_max_
error threshold
Definition: line_iterator.h:101
pcl::LineIterator::error_plus_
int error_plus_
increment of error (distance) value in case of just an x-step (if dx > dy)
Definition: line_iterator.h:107
pcl::LineIterator::getColumnIndex
virtual unsigned getColumnIndex() const
returns the col index (x-coordinate) of the current pixel/point
Definition: line_iterator.h:251
pcl::LineIterator::y_
unsigned y_
current row index
Definition: line_iterator.h:82
pcl::LineIterator::error_
int error_
current distance to the line
Definition: line_iterator.h:98