bresenham.cpp
Go to the documentation of this file.
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2018, Locus Robotics
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 the copyright holder 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 HOLDER 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 
36 #include <cmath>
37 
38 namespace nav_grid_iterators
39 {
40 
41 Bresenham::Bresenham(int x0, int y0, int x1, int y1, bool include_last_index)
42  : AbstractLineIterator(nav_grid::SignedIndex(x0, y0)), x0_(x0), y0_(y0), x1_(x1), y1_(y1),
43  include_last_index_(include_last_index)
44 {
45  int dx = std::abs(x1_ - x0_);
46  int dy = std::abs(y1_ - y0_);
47  int xsign = x1_ >= x0_ ? 1 : -1;
48  int ysign = y1_ >= y0_ ? 1 : -1;
49 
50  if (dx >= dy) // There is at least one x-value for every y-value
51  {
52  loop_inc_x_ = xsign;
53  error_inc_x_ = 0; // Don't change the x when numerator >= denominator
54  loop_inc_y_ = 0; // Don't change the y for every iteration
55  error_inc_y_ = ysign;
56 
57  denominator_ = dx;
58  numerator_ = dx / 2;
59  numerator_inc_ = dy;
60  }
61  else // There is at least one y-value for every x-value
62  {
63  loop_inc_x_ = 0; // Don't change the x for every iteration
64  error_inc_x_ = xsign;
65  loop_inc_y_ = ysign;
66  error_inc_y_ = 0; // Don't change the y when numerator >= denominator
67 
68  denominator_ = dy;
69  numerator_ = dy / 2;
70  numerator_inc_ = dx;
71  }
72 }
73 
75  int x0, int y0, int x1, int y1, bool include_last_index,
76  int error_inc_x, int loop_inc_x, int error_inc_y, int loop_inc_y,
77  int denominator, int numerator, int numerator_inc)
78  : AbstractLineIterator(index), x0_(x0), y0_(y0), x1_(x1), y1_(y1), include_last_index_(include_last_index),
79  error_inc_x_(error_inc_x), loop_inc_x_(loop_inc_x), error_inc_y_(error_inc_y), loop_inc_y_(loop_inc_y),
80  denominator_(denominator), numerator_(numerator), numerator_inc_(numerator_inc)
81 {
82 }
83 
85 {
89 }
90 
92 {
96 
97  // If we want the last_index, return an iterator that is whatever is one-past the end coordinates
99  end.increment();
100  return end;
101 }
102 
104 {
105  numerator_ += numerator_inc_; // Increase the numerator by the top of the fraction
106  if (numerator_ >= denominator_) // Check if numerator >= denominator
107  {
108  numerator_ -= denominator_; // Calculate the new numerator value
109  index_.x += error_inc_x_; // Change the x as appropriate
110  index_.y += error_inc_y_; // Change the y as appropriate
111  }
112  index_.x += loop_inc_x_; // Change the x as appropriate
113  index_.y += loop_inc_y_; // Change the y as appropriate
114 }
115 
117 {
118  return end().index_;
119 }
120 } // namespace nav_grid_iterators
Bresenham(int x0, int y0, int x1, int y1, bool include_last_index=true)
Public constructor.
Definition: bresenham.cpp:41
Abstract class for iterating over lines.
Bresenham end() const
Helper function for range-style iteration.
Definition: bresenham.cpp:91
void increment() override
Increase the iterator to the next element.
Definition: bresenham.cpp:103
Line Iterator using Bresenham&#39;s algorithm (no subpixel precision)
Definition: bresenham.h:46
nav_grid::SignedIndex getFinalIndex() const override
Definition: bresenham.cpp:116
GenericIndex< int > SignedIndex
Bresenham begin() const
Helper function for range-style iteration.
Definition: bresenham.cpp:84


nav_grid_iterators
Author(s):
autogenerated on Sun Jan 10 2021 04:08:42