Embedded Template Library 1.0
bresenham_line.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2020 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_BRESENHAM_LINE_INCLUDED
32#define ETL_BRESENHAM_LINE_INCLUDED
33
34#include "platform.h"
35#include "iterator.h"
36#include "static_assert.h"
37#include "type_traits.h"
38#include "utility.h"
39
40#include <stdint.h>
41
42namespace etl
43{
44 //***************************************************************************
49 //***************************************************************************
50 template <typename T, typename TWork = int16_t>
52 {
53 public:
54
55 //***************************************************
57 //***************************************************
59 typedef size_t size_type;
60 typedef ptrdiff_t difference_type;
61 typedef value_type& reference;
62 typedef const value_type& const_reference;
63 typedef value_type* pointer;
64 typedef const value_type* const_pointer;
65
66 //***************************************************
68 //***************************************************
69 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const value_type>
70 {
71 public:
72
73 friend class bresenham_line;
74
75 //***************************************************
77 //***************************************************
79 : p_bresenham_line(ETL_NULLPTR)
80 {
81 }
82
83 //***************************************************
85 //***************************************************
87 : p_bresenham_line(other.p_bresenham_line)
88 {
89 }
90
91 //***************************************************
93 //***************************************************
95 {
96 p_bresenham_line = rhs.p_bresenham_line;
97
98 return *this;
99 }
100
101 //***************************************************
103 //***************************************************
105 {
106 // Has the end of the series has been reached?
107 if (p_bresenham_line->get_coordinate() == p_bresenham_line->back())
108 {
109 // Mark it as an end iterator.
110 p_bresenham_line = ETL_NULLPTR;
111 }
112 else
113 {
114 p_bresenham_line->next();
115 }
116
117 return *this;
118 }
119
120 //***************************************************
122 //***************************************************
123 value_type operator *() const
124 {
125 return p_bresenham_line->get_coordinate();
126 }
127
128 //***************************************************
130 //***************************************************
131 friend bool operator ==(const const_iterator& lhs, const const_iterator& rhs)
132 {
133 return lhs.p_bresenham_line == rhs.p_bresenham_line;
134 }
135
136 //***************************************************
138 //***************************************************
139 friend bool operator !=(const const_iterator& lhs, const const_iterator& rhs)
140 {
141 return !(lhs == rhs);
142 }
143
144 private:
145
146 //***************************************************
148 //***************************************************
150 : p_bresenham_line(pb)
151 {
152 }
153
154 bresenham_line<T>* p_bresenham_line;
155 };
156
157 //***************************************************
159 //***************************************************
161 {
162 initialise(T(0), T(0), T(0), T(0));
163 }
164
165 //***************************************************
168 //***************************************************
170 {
171 initialise(first_.x, first_.y, last_.x, last_.y);
172 }
173
174 //***************************************************
177 //***************************************************
178 bresenham_line(T first_x, T first_y, T last_x, T last_y)
179 {
180 initialise(first_x, first_y, last_x, last_y);
181 }
182
183 //***************************************************
186 //***************************************************
188 {
189 initialise(first_.x, first_.y, last_.x, last_.y);
190 }
191
192 //***************************************************
195 //***************************************************
196 void reset(T first_x, T first_y, T last_x, T last_y)
197 {
198 initialise(first_x, first_y, last_x, last_y);
199 }
200
201 //***************************************************
204 //***************************************************
206 {
207 coordinate = first;
208
209 return const_iterator(this);
210 }
211
212 //***************************************************
214 //***************************************************
216 {
217 return const_iterator();
218 }
219
220 //***************************************************
222 //***************************************************
224 {
225 return first;
226 }
227
228 //***************************************************
230 //***************************************************
232 {
233 return last;
234 }
235
236 //***************************************************
238 //***************************************************
239 size_t size() const
240 {
241 if (y_is_major_axis())
242 {
243 return (dy / 2) + 1;
244 }
245 else
246 {
247 return (dx / 2) + 1;
248 }
249 }
250
251 //***************************************************
253 //***************************************************
254 friend bool operator ==(const bresenham_line& lhs, const bresenham_line& rhs)
255 {
256 return (lhs.front() == rhs.front()) && (lhs.back() == rhs.back());
257 }
258
259 //***************************************************
261 //***************************************************
262 friend bool operator !=(const bresenham_line& lhs, const bresenham_line& rhs)
263 {
264 return !(lhs == rhs);
265 }
266
267 private:
268
269 //***************************************************
271 //***************************************************
272 void initialise(T first_x, T first_y, T last_x, T last_y)
273 {
274 first = value_type(first_x, first_y);
275 last = value_type(last_x, last_y);
276 coordinate = first;
277 x_increment = (last_x < first_x) ? -1 : 1;
278 y_increment = (last_y < first_y) ? -1 : 1;
279 dx = (last_x < first_x) ? first_x - last_x : last_x - first_x;
280 dy = (last_y < first_y) ? first_y - last_y : last_y - first_y;
281 do_minor_increment = false;
282
283 if (y_is_major_axis())
284 {
285 dx *= 2;
286 balance = dx - dy;
287 dy *= 2;
288 }
289 else
290 {
291 dy *= 2;
292 balance = dy - dx;
293 dx *= 2;
294 }
295 }
296
297 //***************************************************
299 //***************************************************
300 bool y_is_major_axis() const
301 {
302 return dx < dy;
303 }
304
305 //***************************************************
307 //***************************************************
308 void next()
309 {
310 if (y_is_major_axis())
311 {
312 // Y is major axis.
313 if (do_minor_increment)
314 {
315 coordinate.x = T(coordinate.x + x_increment);
316 balance -= dy;
317 }
318
319 coordinate.y = T(coordinate.y + y_increment);
320 balance += dx;
321 }
322 else
323 {
324 // X is major axis.
325 if (do_minor_increment)
326 {
327 coordinate.y = T(coordinate.y + y_increment);
328 balance -= dx;
329 }
330
331 coordinate.x = T(coordinate.x + x_increment);
332 balance += dy;
333 }
334
335 do_minor_increment = (balance >= 0);
336 }
337
338 //***************************************************
340 //***************************************************
341 value_type get_coordinate() const
342 {
343 return coordinate;
344 }
345
346 typedef TWork work_t;
347
348 value_type first;
349 value_type last;
350 value_type coordinate;
351 work_t x_increment;
352 work_t y_increment;
353 work_t dx;
354 work_t dy;
355 work_t balance;
356 bool do_minor_increment;
357 };
358}
359
360#endif
361
Const Iterator.
Definition: bresenham_line.h:70
friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs)
Inequality operator.
Definition: bresenham_line.h:139
const_iterator & operator=(const const_iterator &rhs)
Assignment operator.
Definition: bresenham_line.h:94
const_iterator & operator++()
Pre-increment operator.
Definition: bresenham_line.h:104
const_iterator(const const_iterator &other)
Copy constructor.
Definition: bresenham_line.h:86
friend bool operator==(const const_iterator &lhs, const const_iterator &rhs)
Equality operator.
Definition: bresenham_line.h:131
const_iterator()
Default constructor.
Definition: bresenham_line.h:78
value_type operator*() const
De-reference operator.
Definition: bresenham_line.h:123
Definition: bresenham_line.h:52
const_iterator end() const
Get a const_iterator to one past the last coordinate.
Definition: bresenham_line.h:215
const_iterator begin()
Definition: bresenham_line.h:205
friend bool operator!=(const bresenham_line &lhs, const bresenham_line &rhs)
Inequality operator.
Definition: bresenham_line.h:262
bresenham_line(T first_x, T first_y, T last_x, T last_y)
Definition: bresenham_line.h:178
bresenham_line(etl::coordinate_2d< T > first_, etl::coordinate_2d< T > last_)
Definition: bresenham_line.h:169
void reset(T first_x, T first_y, T last_x, T last_y)
Definition: bresenham_line.h:196
etl::coordinate_2d< T > value_type
Standard container types.
Definition: bresenham_line.h:58
const_reference back() const
Get the last coordinate.
Definition: bresenham_line.h:231
friend bool operator==(const bresenham_line &lhs, const bresenham_line &rhs)
Equality operator.
Definition: bresenham_line.h:254
bresenham_line()
Constructor.
Definition: bresenham_line.h:160
void reset(etl::coordinate_2d< T > first_, etl::coordinate_2d< T > last_)
Definition: bresenham_line.h:187
size_t size() const
Get the size of the series.
Definition: bresenham_line.h:239
const_reference front() const
Get the first coordinate.
Definition: bresenham_line.h:223
bitset_ext
Definition: absolute.h:38
integer_sequence
Definition: utility.h:537
iterator
Definition: iterator.h:399