iLab Neuromorphic Robotics Toolkit  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ConvexPolyIterImpl.H
Go to the documentation of this file.
1 /*! @file
2  @author Unknown
3  @copyright GNU Public License (GPL v3)
4  @section License
5  @verbatim
6  // ////////////////////////////////////////////////////////////////////////
7  // The iLab Neuromorphic Robotics Toolkit (NRT) //
8  // Copyright 2010-2012 by the University of Southern California (USC) //
9  // and the iLab at USC. //
10  // //
11  // iLab - University of Southern California //
12  // Hedco Neurociences Building, Room HNB-10 //
13  // Los Angeles, Ca 90089-2520 - USA //
14  // //
15  // See http://ilab.usc.edu for information about this project. //
16  // ////////////////////////////////////////////////////////////////////////
17  // This file is part of The iLab Neuromorphic Robotics Toolkit. //
18  // //
19  // The iLab Neuromorphic Robotics Toolkit is free software: you can //
20  // redistribute it and/or modify it under the terms of the GNU General //
21  // Public License as published by the Free Software Foundation, either //
22  // version 3 of the License, or (at your option) any later version. //
23  // //
24  // The iLab Neuromorphic Robotics Toolkit is distributed in the hope //
25  // that it will be useful, but WITHOUT ANY WARRANTY; without even the //
26  // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR //
27  // PURPOSE. See the GNU General Public License for more details. //
28  // //
29  // You should have received a copy of the GNU General Public License //
30  // along with The iLab Neuromorphic Robotics Toolkit. If not, see //
31  // <http://www.gnu.org/licenses/>. //
32  // ////////////////////////////////////////////////////////////////////////
33  @endverbatim */
34 
35 // ######################################################################
36 // Convex Polygon Iterator
37 // Limitations of the Polygon Iterator
38 // Only works with convex polygons
39 // Limited to width,height < 2^16, because of integer shifting operations assumptions
40 
41 template<class T, nrt::uint32 Flags>
42 class nrt::Image<T, Flags>::convex_poly_iterator
43  : public boost::iterator_facade<nrt::Image<T, Flags>::convex_poly_iterator, T, boost::incrementable_traversal_tag>
44 {
45  public:
46  inline convex_poly_iterator(T *p, nrt::Polygon<nrt::int32> const & poly, Dims<nrt::int32> imageDims)
47  : itsOrigPtr(p), itsCurPtr(p), itsPolygon(poly), itsImageDims(imageDims)
48  {
49  // Null ptr is set for end iterator
50  if(!itsCurPtr)
51  {
52  itsEdgeCount=0;
53  itsCount3=itsCount2=itsCount1=0;
54  return;
55  }
56  itsEdgeCount = itsPolygon.vertices().size();
57  itsNumEdges = itsPolygon.vertices().size();
58  itsMinY = itsPolygon.vertices()[0].y();
59  itsStartV1 = 0;
60  for(uint c= 1; c < itsPolygon.vertices().size(); c++) //Find Top Vertex
61  {
62  if (itsPolygon.vertices()[c].y() < itsMinY)
63  {
64  itsMinY = itsPolygon.vertices()[c].y();
65  itsStartV1 = c;
66  }
67  }
68  itsStartV2 = itsStartV1;
69  itsEndV1 = itsStartV1 - 1;
70  if(itsEndV1 < 0) itsEndV1 = (itsNumEdges-1);
71 
72  itsEndV2 = itsStartV2 + 1;
73  if (itsEndV2 >= itsNumEdges) itsEndV2 = 0;
74  itsMinY = itsPolygon.vertices()[itsStartV1].y();
75 
76  int x1 = itsPolygon.vertices()[itsStartV1].x(); int y1 = itsPolygon.vertices()[itsStartV1].y();
77  int x2 = itsPolygon.vertices()[itsEndV1].x(); int y2 = itsPolygon.vertices()[itsEndV1].y();
78 
79  itsDx1 = ((x2 - x1) << 16) / (y2 - y1 + 1);
80  itsCount1 = y2-y1;
81  itsXVal1 = x1 << 16;
82 
83  int x11 = itsPolygon.vertices()[itsStartV2].x(); int y11 = itsPolygon.vertices()[itsStartV2].y();
84  int x22 = itsPolygon.vertices()[itsEndV2].x(); int y22 = itsPolygon.vertices()[itsEndV2].y();
85 
86  itsDx2 = ((x22 - x11) << 16) / (y22 - y11 + 1);
87  itsCount2 = y22-y11;
88  itsXVal2 = x11 << 16;
89 
90  itsCount3 = x11-x1;
91  itsCurPtr += itsMinY*itsImageDims.width() + x1;
92  }
93 
94  inline nrt::Point2D<nrt::int32> location()
95  {
96  return Point2D<nrt::int32>((itsXVal2>>16)-itsCount3,itsMinY);
97  }
98 
99 
100  private:
101  friend class boost::iterator_core_access;
102 
103  inline void increment()
104  {
105  if(itsCount3 > 0)
106  {
107  itsCount3--;
108  itsCurPtr++;
109  }
110  else if (itsEdgeCount > 1)
111  {
112  while( itsEdgeCount > 1 && (itsCount1 == 0 || itsCount2 == 0) )
113  {
114  if (itsCount1 == 0)
115  {
116  itsEdgeCount--;
117  itsStartV1 = itsEndV1;
118  itsEndV1--;
119  if (itsEndV1 < 0) itsEndV1 = itsNumEdges-1;
120 
121  itsMinY = itsPolygon.vertices()[itsStartV1].y();
122  nrt::int32 x1 = itsPolygon.vertices()[itsStartV1].x(), y1 = itsPolygon.vertices()[itsStartV1].y();
123  nrt::int32 x2 = itsPolygon.vertices()[itsEndV1].x(), y2 = itsPolygon.vertices()[itsEndV1].y();
124  itsDx1 = ((x2 - x1) << 16) / (abs(y2 - y1) + 1);
125  itsCount1 = y2-y1;
126  itsXVal1 = x1 << 16;
127  }
128  if (itsCount2 == 0)
129  {
130  itsEdgeCount--;
131  itsStartV2 = itsEndV2;
132  itsEndV2++;
133  if(itsEndV2 >= itsNumEdges) itsEndV2 = 0;
134  itsMinY = itsPolygon.vertices()[itsStartV2].y();
135  nrt::int32 x11 = itsPolygon.vertices()[itsStartV2].x(), y11 = itsPolygon.vertices()[itsStartV2].y();
136  nrt::int32 x22 = itsPolygon.vertices()[itsEndV2].x(), y22 = itsPolygon.vertices()[itsEndV2].y();
137  itsDx2 = ((x22 - x11) << 16) / (abs(y22 - y11) + 1);
138  itsCount2 = y22-y11;
139  itsXVal2 = x11 << 16;
140  }
141  }
142  if ( (itsCount1 > 0) && (itsCount2 > 0) )
143  {
144  itsXVal1 += itsDx1; itsXVal2 += itsDx2;
145  itsCount1--; itsCount2--;
146  itsMinY++;
147  nrt::int32 x1 = itsXVal1 >> 16;
148  nrt::int32 x2 = itsXVal2 >> 16;
149  itsCount3=x2-x1;
150  itsCurPtr = itsOrigPtr + itsMinY*itsImageDims.width() + x1;
151  }
152  else
153  {
154  itsCurPtr = NULL;
155  }
156  }
157  else
158  {
159  itsCurPtr = NULL;
160  }
161 
162  }
163 
164  inline bool equal(nrt::Image<T, Flags>::convex_poly_iterator const& other) const
165  { return itsCurPtr == other.itsCurPtr; }
166 
167  inline T & dereference() const { return *itsCurPtr; }
168 
169 
170  private:
171  // Reference to the begin(), needed when we jump
172  T * const itsOrigPtr;
173  // Reference to the current pointer
174  T * itsCurPtr;
175  // Polygon to iterate over
176  const nrt::Polygon<nrt::int32> itsPolygon;
177  // Dimensions of image
178  const nrt::Dims<nrt::int32> itsImageDims;
179  // Start and end points of the left edge (V1) and right edge (V2)
180  nrt::int32 itsStartV1,itsStartV2,itsEndV1,itsEndV2;
181  // Current left (itsXVal1) and right (itsXVal2) bounding x positions for the current row (itsMinY)
182  nrt::int32 itsXVal1,itsXVal2,itsMinY;
183  // Amount of delta to change of x on left side (itsDx1) and right side (itsDx2) for each increment of y
184  nrt::int32 itsDx1,itsDx2;
185  // Remaining height of left side (itsCount1) or right size (itsCount2) edges heading to the next vertex from the prior vertex.
186  nrt::int32 itsCount1,itsCount2;
187  // Remaining width of the current row (itsCount3)
188  nrt::int32 itsCount3;
189  // Remaining number of edges in polygon
190  nrt::int32 itsEdgeCount;
191  // Total number of edges in polygon
192  nrt::int32 itsNumEdges;
193 };
194 
195 // ######################################################################
196 template<class T, nrt::uint32 Flags> inline
198  nrt::Polygon<nrt::int32> const &polygon)
199 {
202 }
203 
204 // ######################################################################
205 template<class T, nrt::uint32 Flags> inline
207  nrt::Polygon<nrt::int32> const &polygon)
208 {
210 }
211 
212 // ######################################################################
213 template<class T, nrt::uint32 Flags>
214 class nrt::Image<T, Flags>::const_convex_poly_iterator
215  : public boost::iterator_facade<nrt::Image<T, Flags>::const_convex_poly_iterator, const T, boost::incrementable_traversal_tag>
216 {
217  public:
218  inline const_convex_poly_iterator(T const *p, nrt::Polygon<nrt::int32> const & poly, Dims<nrt::int32> imageDims)
219  : itsOrigPtr(p), itsCurPtr(p), itsPolygon(poly), itsImageDims(imageDims)
220  {
221  // Null ptr is set for end iterator
222  if(!itsCurPtr)
223  {
224  itsEdgeCount=0;
225  itsCount3=itsCount2=itsCount1=0;
226  return;
227  }
228  itsEdgeCount = itsPolygon.vertices().size();
229  itsNumEdges = itsPolygon.vertices().size();
230  itsMinY = itsPolygon.vertices()[0].y();
231  itsStartV1 = 0;
232  for(uint c= 1; c < itsPolygon.vertices().size(); c++) //Find Top Vertex
233  {
234  if (itsPolygon.vertices()[c].y() < itsMinY)
235  {
236  itsMinY = itsPolygon.vertices()[c].y();
237  itsStartV1 = c;
238  }
239  }
240  itsStartV2 = itsStartV1;
241  itsEndV1 = itsStartV1 - 1;
242  if(itsEndV1 < 0) itsEndV1 = (itsNumEdges-1);
243 
244  itsEndV2 = itsStartV2 + 1;
245  if (itsEndV2 >= itsNumEdges) itsEndV2 = 0;
246  itsMinY = itsPolygon.vertices()[itsStartV1].y();
247 
248  int x1 = itsPolygon.vertices()[itsStartV1].x(); int y1 = itsPolygon.vertices()[itsStartV1].y();
249  int x2 = itsPolygon.vertices()[itsEndV1].x(); int y2 = itsPolygon.vertices()[itsEndV1].y();
250 
251  itsDx1 = ((x2 - x1) << 16) / (y2 - y1 + 1);
252  itsCount1 = y2-y1;
253  itsXVal1 = x1 << 16;
254 
255  int x11 = itsPolygon.vertices()[itsStartV2].x(); int y11 = itsPolygon.vertices()[itsStartV2].y();
256  int x22 = itsPolygon.vertices()[itsEndV2].x(); int y22 = itsPolygon.vertices()[itsEndV2].y();
257 
258  itsDx2 = ((x22 - x11) << 16) / (y22 - y11 + 1);
259  itsCount2 = y22-y11;
260  itsXVal2 = x11 << 16;
261 
262  itsCount3 = x11-x1;
263  itsCurPtr += itsMinY*itsImageDims.width() + x1;
264  }
265 
266  inline nrt::Point2D<nrt::int32> location()
267  {
268  return Point2D<nrt::int32>((itsXVal2>>16)-itsCount3,itsMinY);
269  }
270 
271 
272  private:
273  friend class boost::iterator_core_access;
274 
275  inline void increment()
276  {
277  if(itsCount3 > 0)
278  {
279  itsCount3--;
280  itsCurPtr++;
281  }
282  else if (itsEdgeCount > 1)
283  {
284  while( itsEdgeCount > 1 && (itsCount1 == 0 || itsCount2 == 0) )
285  {
286  if (itsCount1 == 0)
287  {
288  itsEdgeCount--;
289  itsStartV1 = itsEndV1;
290  itsEndV1--;
291  if (itsEndV1 < 0) itsEndV1 = itsNumEdges-1;
292 
293  itsMinY = itsPolygon.vertices()[itsStartV1].y();
294  nrt::int32 x1 = itsPolygon.vertices()[itsStartV1].x(), y1 = itsPolygon.vertices()[itsStartV1].y();
295  nrt::int32 x2 = itsPolygon.vertices()[itsEndV1].x(), y2 = itsPolygon.vertices()[itsEndV1].y();
296  itsDx1 = ((x2 - x1) << 16) / (abs(y2 - y1) + 1);
297  itsCount1 = y2-y1;
298  itsXVal1 = x1 << 16;
299  }
300  if (itsCount2 == 0)
301  {
302  itsEdgeCount--;
303  itsStartV2 = itsEndV2;
304  itsEndV2++;
305  if(itsEndV2 >= itsNumEdges) itsEndV2 = 0;
306  itsMinY = itsPolygon.vertices()[itsStartV2].y();
307  nrt::int32 x11 = itsPolygon.vertices()[itsStartV2].x(), y11 = itsPolygon.vertices()[itsStartV2].y();
308  nrt::int32 x22 = itsPolygon.vertices()[itsEndV2].x(), y22 = itsPolygon.vertices()[itsEndV2].y();
309  itsDx2 = ((x22 - x11) << 16) / (abs(y22 - y11) + 1);
310  itsCount2 = y22-y11;
311  itsXVal2 = x11 << 16;
312  }
313  }
314  if ( (itsCount1 > 0) && (itsCount2 > 0) )
315  {
316  itsXVal1 += itsDx1; itsXVal2 += itsDx2;
317  itsCount1--; itsCount2--;
318  itsMinY++;
319  nrt::int32 x1 = itsXVal1 >> 16;
320  nrt::int32 x2 = itsXVal2 >> 16;
321  itsCount3=x2-x1;
322  itsCurPtr = itsOrigPtr + itsMinY*itsImageDims.width() + x1;
323  }
324  else
325  {
326  itsCurPtr = NULL;
327  }
328  }
329  else
330  {
331  itsCurPtr = NULL;
332  }
333 
334  }
335 
336  inline bool equal(nrt::Image<T, Flags>::const_convex_poly_iterator const& other) const
337  { return itsCurPtr == other.itsCurPtr; }
338 
339  inline T const & dereference() const { return *itsCurPtr; }
340 
341 
342  private:
343  // Reference to the begin(), needed when we jump
344  const T * const itsOrigPtr;
345  // Reference to the current pointer
346  const T * itsCurPtr;
347  // Polygon to iterate over
348  const nrt::Polygon<nrt::int32> itsPolygon;
349  // Dimensions of image
350  const nrt::Dims<nrt::int32> itsImageDims;
351  // Start and end points of the left edge (V1) and right edge (V2)
352  nrt::int32 itsStartV1,itsStartV2,itsEndV1,itsEndV2;
353  // Current left (itsXVal1) and right (itsXVal2) bounding x positions for the current row (itsMinY)
354  nrt::int32 itsXVal1,itsXVal2,itsMinY;
355  // Amount of delta to change of x on left side (itsDx1) and right side (itsDx2) for each increment of y
356  nrt::int32 itsDx1,itsDx2;
357  // Remaining height of left side (itsCount1) or right size (itsCount2) edges heading to the next vertex from the prior vertex.
358  nrt::int32 itsCount1,itsCount2;
359  // Remaining width of the current row (itsCount3)
360  nrt::int32 itsCount3;
361  // Remaining number of edges in polygon
362  nrt::int32 itsEdgeCount;
363  // Total number of edges in polygon
364  nrt::int32 itsNumEdges;
365 };
366 
367 // ######################################################################
368 template<class T, nrt::uint32 Flags> inline
370  nrt::Polygon<nrt::int32> const &polygon) const
371 {
373 }
374 
375 // ######################################################################
376 template<class T, nrt::uint32 Flags> inline
378  nrt::Polygon<nrt::int32> const &polygon) const
379 {
381 }
382 
383 // ######################################################################
384 template<class T, nrt::uint32 Flags> inline
386  nrt::Polygon<nrt::int32> const &polygon) const
387 {
389  ( nrt::Array2D<T>::itsArray.const_begin(),polygon, nrt::Array2D<T>::itsDims);
390 }
391 
392 // ######################################################################
393 template<class T, nrt::uint32 Flags> inline
395  nrt::Polygon<nrt::int32> const &polygon) const
396 {
398 }
399 
400 // Need to handle algorithms that need a local surround when doing operations on a polygon...
401 // Some concept of location of iterator is essential, also distance to image border is important