Point Cloud Library (PCL)  1.14.0-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
43  * using the Bresenham algorithm. 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 public:
50  /** \brief Neighborhood connectivity */
51  enum Neighborhood { Neighbor4 = 4, Neighbor8 = 8 };
52 
53 public:
54  /**
55  * \brief Constructor
56  * \param x_start column of the start pixel of the line
57  * \param y_start row of the start pixel of the line
58  * \param x_end column of the end pixel of the line
59  * \param y_end row of the end pixel of the line
60  * \param width width of the organized structure e.g. image/cloud/map etc..
61  * \param neighborhood connectivity of the neighborhood
62  */
63  LineIterator(unsigned x_start,
64  unsigned y_start,
65  unsigned x_end,
66  unsigned y_end,
67  unsigned width,
68  const Neighborhood& neighborhood = Neighbor8);
69 
70  /** \brief Destructor*/
71  ~LineIterator() override;
72 
73  void
74  operator++() override;
75  unsigned
76  getRowIndex() const override;
77  unsigned
78  getColumnIndex() const override;
79  bool
80  isValid() const override;
81  void
82  reset() override;
83 
84 protected:
85  /**
86  * \brief initializes the variables for the Bresenham algorithm
87  * \param[in] neighborhood connectivity to the neighborhood. Either 4 or 8
88  */
89  void
90  init(const Neighborhood& neighborhood);
91 
92  /** \brief current column index*/
93  unsigned x_;
94 
95  /** \brief current row index*/
96  unsigned y_;
97 
98  /** \brief column index of first pixel/point*/
99  unsigned x_start_;
100 
101  /** \brief row index of first pixel/point*/
102  unsigned y_start_;
103 
104  /** \brief column index of end pixel/point*/
105  unsigned x_end_;
106 
107  /** \brief row index of end pixel/point*/
108  unsigned y_end_;
109 
110  // calculated values
111  /** \brief current distance to the line*/
112  int error_;
113 
114  /** \brief error threshold*/
116 
117  /** \brief increment of error (distance) value in case of an y-step (if dx > dy)*/
119 
120  /** \brief increment of error (distance) value in case of just an x-step (if dx >
121  * dy)*/
123 
124  /** \brief increment of column index in case of just an x-step (if dx > dy)*/
125  int x_plus_;
126 
127  /** \brief increment of row index in case of just an x-step (if dx > dy)*/
128  int y_plus_;
129 
130  /** \brief increment of column index in case of just an y-step (if dx > dy)*/
131  int x_minus_;
132 
133  /** \brief increment of row index in case of just an y-step (if dx > dy)*/
134  int y_minus_;
135 
136  /** \brief increment pixel/point index in case of just an x-step (if dx > dy)*/
138 
139  /** \brief increment pixel/point index in case of just an y-step (if dx > dy)*/
141 };
142 
143 ////////////////////////////////////////////////////////////////////////////////
144 ////////////////////////////////////////////////////////////////////////////////
145 ////////////////////////////////////////////////////////////////////////////////
146 
147 ////////////////////////////////////////////////////////////////////////////////
148 inline LineIterator::LineIterator(unsigned x_start,
149  unsigned y_start,
150  unsigned x_end,
151  unsigned y_end,
152  unsigned width,
153  const Neighborhood& neighborhood)
154 : OrganizedIndexIterator(width)
155 , x_start_(x_start)
156 , y_start_(y_start)
157 , x_end_(x_end)
158 , y_end_(y_end)
159 {
160  init(neighborhood);
161 }
162 
163 ////////////////////////////////////////////////////////////////////////////////
164 inline LineIterator::~LineIterator() = default;
165 
166 ////////////////////////////////////////////////////////////////////////////////
167 inline void
168 LineIterator::init(const Neighborhood& neighborhood)
169 {
170  x_ = x_start_;
171  y_ = y_start_;
172  index_ = x_ * width_ + y_;
173  error_ = 0;
174 
175  int delta_x = x_end_ - x_start_;
176  int delta_y = y_end_ - y_start_;
177 
178  int x_dir = ((delta_x > 0) ? 1 : -1);
179  int y_dir = ((delta_y > 0) ? 1 : -1);
180 
181  delta_x *= x_dir;
182  delta_y *= y_dir;
183 
184  if (delta_x >= delta_y) {
185  if (neighborhood == Neighbor4) {
186  error_max_ = delta_x - delta_y;
187  x_minus_ = 0;
188  y_minus_ = y_dir;
189  x_plus_ = x_dir;
190  y_plus_ = 0;
191 
192  error_minus_ = -(delta_x * 2);
193  error_plus_ = (delta_y * 2);
194  }
195  else {
196  error_max_ = delta_x - (delta_y * 2);
197  x_minus_ = x_dir;
198  y_minus_ = y_dir;
199  x_plus_ = x_dir;
200  y_plus_ = 0;
201 
202  error_minus_ = (delta_y - delta_x) * 2;
203  error_plus_ = (delta_y * 2);
204  }
205  }
206  else {
207  if (neighborhood == Neighbor4) {
208  error_max_ = delta_y - delta_x;
209  x_minus_ = x_dir;
210  y_minus_ = 0;
211  x_plus_ = 0;
212  y_plus_ = y_dir;
213 
214  error_minus_ = -(delta_y * 2);
215  error_plus_ = (delta_x * 2);
216  }
217  else {
218  error_max_ = delta_y - (delta_x * 2);
219  x_minus_ = x_dir;
220  y_minus_ = y_dir;
221  x_plus_ = 0;
222  y_plus_ = y_dir;
223 
224  error_minus_ = (delta_x - delta_y) * 2;
225  error_plus_ = (delta_x * 2);
226  }
227  }
228 
231 }
232 
233 ////////////////////////////////////////////////////////////////////////////////
234 inline void
236 {
237  if (error_ >= error_max_) {
238  x_ += x_minus_;
239  y_ += y_minus_;
240  error_ += error_minus_;
241  index_ += index_minus_;
242  }
243  else {
244  x_ += x_plus_;
245  y_ += y_plus_;
246  error_ += error_plus_;
247  index_ += index_plus_;
248  }
249 }
250 
251 ////////////////////////////////////////////////////////////////////////////////
252 inline unsigned
254 {
255  return y_;
256 }
257 
258 ////////////////////////////////////////////////////////////////////////////////
259 inline unsigned
261 {
262  return x_;
263 }
264 
265 ////////////////////////////////////////////////////////////////////////////////
266 inline bool
268 {
269  return (x_ != x_end_ || y_ != y_end_);
270 }
271 
272 ////////////////////////////////////////////////////////////////////////////////
273 inline void
275 {
276  x_ = x_start_;
277  y_ = y_start_;
278  error_ = 0;
279  index_ = x_ * width_ + y_;
280 }
281 
282 } // namespace pcl
Organized Index Iterator for iterating over the "pixels" for a given line using the Bresenham algorit...
Definition: line_iterator.h:48
unsigned x_end_
column index of end pixel/point
void operator++() override
go to next pixel/point in image/cloud
int y_minus_
increment of row index in case of just an y-step (if dx > dy)
unsigned getColumnIndex() const override
returns the col index (x-coordinate) of the current pixel/point
int index_minus_
increment pixel/point index in case of just an y-step (if dx > dy)
unsigned y_
current row index
Definition: line_iterator.h:96
void reset() override
resets the iterator to the beginning of the line
int x_minus_
increment of column index in case of just an y-step (if dx > dy)
unsigned getRowIndex() const override
returns the row index (y-coordinate) of the current pixel/point
unsigned y_end_
row index of end pixel/point
LineIterator(unsigned x_start, unsigned y_start, unsigned x_end, unsigned y_end, unsigned width, const Neighborhood &neighborhood=Neighbor8)
Constructor.
int error_minus_
increment of error (distance) value in case of an y-step (if dx > dy)
int error_plus_
increment of error (distance) value in case of just an x-step (if dx > dy)
~LineIterator() override
Destructor.
void init(const Neighborhood &neighborhood)
initializes the variables for the Bresenham algorithm
Neighborhood
Neighborhood connectivity
Definition: line_iterator.h:51
int y_plus_
increment of row index in case of just an x-step (if dx > dy)
int index_plus_
increment pixel/point index in case of just an x-step (if dx > dy)
int x_plus_
increment of column index in case of just an x-step (if dx > dy)
unsigned x_
current column index
Definition: line_iterator.h:93
unsigned y_start_
row index of first pixel/point
int error_max_
error threshold
int error_
current distance to the line
unsigned x_start_
column index of first pixel/point
Definition: line_iterator.h:99
bool isValid() const override
return whether the current visited pixel/point is valid or not.
base class for iterators on 2-dimensional maps like images/organized clouds etc.
unsigned width_
the width of the image/cloud
unsigned index_
the index of the current pixel/point