Point Cloud Library (PCL)  1.9.1-dev
line_iterator.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2010, Willow Garage, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above
14  * copyright notice, this list of conditions and the following
15  * disclaimer in the documentation and/or other materials provided
16  * with the distribution.
17  * * Neither the name of Willow Garage, Inc. nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  */
35 
36 #pragma once
37 
38 #include "organized_index_iterator.h"
39 
40 namespace pcl
41 {
42 /** \brief Organized Index Iterator for iterating over the "pixels" for a given line using the Bresenham algorithm.
43  * Supports 4 and 8 neighborhood connectivity
44  * \note iterator does not visit the given end-point (on purpose).
45  * \author Suat Gedikli <gedikli@willowgarage.com>
46  * \ingroup geometry
47  */
49 {
50  public:
51  /** \brief Neighborhood connectivity */
52  enum Neighborhood {Neighbor4 = 4, Neighbor8 = 8};
53  public:
54  /** \brief Constructor
55  * \param x_start column of the start pixel of the line
56  * \param y_start row of the start pixel of the line
57  * \param x_end column of the end pixel of the line
58  * \param y_end row of the end pixel of the line
59  * \param width width of the organized structure e.g. image/cloud/map etc..
60  * \param neighborhood connectivity of the neighborhood
61  */
62  LineIterator (unsigned x_start, unsigned y_start, unsigned x_end, unsigned y_end, unsigned width, const Neighborhood& neighborhood = Neighbor8);
63 
64  /** \brief Destructor*/
65  ~LineIterator ();
66 
67  void operator ++ () override;
68  unsigned getRowIndex () const override;
69  unsigned getColumnIndex () const override;
70  bool isValid () const override;
71  void reset () override;
72  protected:
73  /** \brief initializes the variables for the Bresenham algorithm
74  * \param[in] neighborhood connectivity to the neighborhood. Either 4 or 8
75  */
76  void init (const Neighborhood& neighborhood);
77 
78  /** \brief current column index*/
79  unsigned x_;
80 
81  /** \brief current row index*/
82  unsigned y_;
83 
84  /** \brief column index of first pixel/point*/
85  unsigned x_start_;
86 
87  /** \brief row index of first pixel/point*/
88  unsigned y_start_;
89 
90  /** \brief column index of end pixel/point*/
91  unsigned x_end_;
92 
93  /** \brief row index of end pixel/point*/
94  unsigned y_end_;
95 
96  // calculated values
97  /** \brief current distance to the line*/
98  int error_;
99 
100  /** \brief error threshold*/
102 
103  /** \brief increment of error (distance) value in case of an y-step (if dx > dy)*/
105 
106  /** \brief increment of error (distance) value in case of just an x-step (if dx > dy)*/
108 
109  /** \brief increment of column index in case of just an x-step (if dx > dy)*/
110  int x_plus_;
111 
112  /** \brief increment of row index in case of just an x-step (if dx > dy)*/
113  int y_plus_;
114 
115  /** \brief increment of column index in case of just an y-step (if dx > dy)*/
116  int x_minus_;
117 
118  /** \brief increment of row index in case of just an y-step (if dx > dy)*/
119  int y_minus_;
120 
121  /** \brief increment pixel/point index in case of just an x-step (if dx > dy)*/
123 
124  /** \brief increment pixel/point index in case of just an y-step (if dx > dy)*/
126 };
127 
128 ////////////////////////////////////////////////////////////////////////////////
129 ////////////////////////////////////////////////////////////////////////////////
130 ////////////////////////////////////////////////////////////////////////////////
131 
132 
133 ////////////////////////////////////////////////////////////////////////////////
134 inline LineIterator::LineIterator (unsigned x_start, unsigned y_start, unsigned x_end, unsigned y_end, unsigned width, const Neighborhood& neighborhood)
135 : OrganizedIndexIterator (width)
136 , x_start_ (x_start)
137 , y_start_ (y_start)
138 , x_end_ (x_end)
139 , y_end_ (y_end)
140 {
141  init (neighborhood);
142 }
143 
144 ////////////////////////////////////////////////////////////////////////////////
146 {
147 }
148 
149 ////////////////////////////////////////////////////////////////////////////////
150 inline void
151 LineIterator::init (const Neighborhood& neighborhood)
152 {
153  x_ = x_start_;
154  y_ = y_start_;
155  index_ = x_ * width_ + y_;
156  error_ = 0;
157 
158  int delta_x = x_end_ - x_start_;
159  int delta_y = y_end_ - y_start_;
160 
161  int x_dir = ( (delta_x > 0) ? 1 : -1 ) ;
162  int y_dir = ( (delta_y > 0) ? 1 : -1 ) ;
163 
164  delta_x *= x_dir;
165  delta_y *= y_dir;
166 
167  if(delta_x >= delta_y)
168  {
169  if( neighborhood == Neighbor4 )
170  {
171  error_max_ = delta_x - delta_y;
172  x_minus_ = 0;
173  y_minus_ = y_dir;
174  x_plus_ = x_dir;
175  y_plus_ = 0;
176 
177  error_minus_ = -(delta_x * 2);
178  error_plus_ = (delta_y * 2);
179  }
180  else
181  {
182  error_max_ = delta_x - (delta_y * 2);
183  x_minus_ = x_dir;
184  y_minus_ = y_dir;
185  x_plus_ = x_dir;
186  y_plus_ = 0;
187 
188  error_minus_ = (delta_y - delta_x) * 2;
189  error_plus_ = (delta_y * 2);
190  }
191  }
192  else
193  {
194  if( neighborhood == Neighbor4 )
195  {
196  error_max_ = delta_y - delta_x;
197  x_minus_ = x_dir;
198  y_minus_ = 0;
199  x_plus_ = 0;
200  y_plus_ = y_dir;
201 
202  error_minus_ = -(delta_y * 2);
203  error_plus_ = (delta_x * 2);
204  }
205  else
206  {
207  error_max_ = delta_y - (delta_x * 2);
208  x_minus_ = x_dir;
209  y_minus_ = y_dir;
210  x_plus_ = 0;
211  y_plus_ = y_dir;
212 
213  error_minus_ = (delta_x - delta_y) * 2;
214  error_plus_ = (delta_x * 2);
215  }
216  }
217 
220 }
221 
222 ////////////////////////////////////////////////////////////////////////////////
223 inline void
225 {
226  if (error_ >= error_max_ )
227  {
228  x_ += x_minus_;
229  y_ += y_minus_;
230  error_ += error_minus_;
231  index_ += index_minus_;
232  }
233  else
234  {
235  x_ += x_plus_;
236  y_ += y_plus_;
237  error_ += error_plus_;
238  index_ += index_plus_;
239  }
240 }
241 
242 ////////////////////////////////////////////////////////////////////////////////
243 inline unsigned
245 {
246  return y_;
247 }
248 
249 ////////////////////////////////////////////////////////////////////////////////
250 inline unsigned
252 {
253  return x_;
254 }
255 
256 ////////////////////////////////////////////////////////////////////////////////
257 inline bool
259 {
260  return (x_ != x_end_ || y_ != y_end_);
261 }
262 
263 ////////////////////////////////////////////////////////////////////////////////
264 inline void
266 {
267  x_ = x_start_;
268  y_ = y_start_;
269  error_ = 0;
270  index_ = x_ * width_ + y_;
271 }
272 
273 } // namespace pcl
unsigned index_
the index of the current pixel/point
void reset() override
resets the iterator to the beginning of the line
int index_plus_
increment pixel/point index in case of just an x-step (if dx > dy)
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:45
~LineIterator()
Destructor.
Neighborhood
Neighborhood connectivity.
Definition: line_iterator.h:52
void operator++() override
go to next pixel/point in image/cloud
int index_minus_
increment pixel/point index in case of just an y-step (if dx > dy)
int y_plus_
increment of row index in case of just an x-step (if dx > dy)
unsigned y_start_
row index of first pixel/point
Definition: line_iterator.h:88
void init(const Neighborhood &neighborhood)
initializes the variables for the Bresenham algorithm
int y_minus_
increment of row index in case of just an y-step (if dx > dy)
unsigned x_end_
column index of end pixel/point
Definition: line_iterator.h:91
unsigned x_start_
column index of first pixel/point
Definition: line_iterator.h:85
Organized Index Iterator for iterating over the "pixels" for a given line using the Bresenham algorit...
Definition: line_iterator.h:48
LineIterator(unsigned x_start, unsigned y_start, unsigned x_end, unsigned y_end, unsigned width, const Neighborhood &neighborhood=Neighbor8)
Constructor.
base class for iterators on 2-dimensional maps like images/organized clouds etc.
unsigned getRowIndex() const override
returns the row index (y-coordinate) of the current pixel/point
unsigned x_
current column index
Definition: line_iterator.h:79
int x_minus_
increment of column index in case of just an y-step (if dx > dy)
unsigned y_end_
row index of end pixel/point
Definition: line_iterator.h:94
int error_minus_
increment of error (distance) value in case of an y-step (if dx > dy)
int x_plus_
increment of column index in case of just an x-step (if dx > dy)
unsigned width_
the width of the image/cloud
int error_max_
error threshold
int error_plus_
increment of error (distance) value in case of just an x-step (if dx > dy)
unsigned getColumnIndex() const override
returns the col index (x-coordinate) of the current pixel/point
bool isValid() const override
return whether the current visited pixel/point is valid or not.
unsigned y_
current row index
Definition: line_iterator.h:82
int error_
current distance to the line
Definition: line_iterator.h:98