MIRA
RasterPolygonUtils.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) by
3  * MetraLabs GmbH (MLAB), GERMANY
4  * and
5  * Neuroinformatics and Cognitive Robotics Labs (NICR) at TU Ilmenau, GERMANY
6  * All rights reserved.
7  *
8  * Contact: info@mira-project.org
9  *
10  * Commercial Usage:
11  * Licensees holding valid commercial licenses may use this file in
12  * accordance with the commercial license agreement provided with the
13  * software or, alternatively, in accordance with the terms contained in
14  * a written agreement between you and MLAB or NICR.
15  *
16  * GNU General Public License Usage:
17  * Alternatively, this file may be used under the terms of the GNU
18  * General Public License version 3.0 as published by the Free Software
19  * Foundation and appearing in the file LICENSE.GPL3 included in the
20  * packaging of this file. Please review the following information to
21  * ensure the GNU General Public License version 3.0 requirements will be
22  * met: http://www.gnu.org/copyleft/gpl.html.
23  * Alternatively you may (at your option) use any later version of the GNU
24  * General Public License if such license has been publicly approved by
25  * MLAB and NICR (or its successors, if any).
26  *
27  * IN NO EVENT SHALL "MLAB" OR "NICR" BE LIABLE TO ANY PARTY FOR DIRECT,
28  * INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF
29  * THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF "MLAB" OR
30  * "NICR" HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  *
32  * "MLAB" AND "NICR" SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
33  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
34  * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
35  * ON AN "AS IS" BASIS, AND "MLAB" AND "NICR" HAVE NO OBLIGATION TO
36  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS OR MODIFICATIONS.
37  */
38 
47 #ifndef _MIRA_BASE_INCLUDE_GEOMETRY_RASTERPOLYGONUTILS_H_
48 #define _MIRA_BASE_INCLUDE_GEOMETRY_RASTERPOLYGONUTILS_H_
49 
50 #include <algorithm>
51 #include <geometry/Polygon.h>
52 
53 namespace mira { namespace Private {
54 
56 
57 class EdgeCuts
58 {
59  // Class that generates cuts of an edge with a grid
60 public:
61  EdgeCuts(Point2f start, Point2f end)
62  {
63  if (start.y() < end.y()) {
64  std::swap(start, end);
65  }
66  // y is descending from start to end
67 
68  // x = m*y + n
69  const auto m = (end.x() - start.x()) / (end.y() - start.y());
70  const auto n = start.x() - m * start.y();
71 
72  auto startY = (int)std::round(start.y());
73  auto endY = (int)std::round(end.y());
74 
75  const float currentGrid = startY - 0.5;
76  mCurrentCut = m * currentGrid + n;
77 
78  mNumberOfCutsWithGrid = startY - endY;
79  // m*y + n = x
80  // m*(y - 1) + n = m*y + n - m = x - m
81  mDeltaToNextCut = -m;
82  mMaxY = startY - 1;
83  }
84 
85  inline int getMaxY() const
86  {
87  return mMaxY;
88  }
89 
90  inline int getNumberOfCutsWithGrid() const
91  {
92  return mNumberOfCutsWithGrid;
93  }
94 
95  inline bool hasCuts() const
96  {
97  return mNumberOfCutsWithGrid > 0;
98  }
99 
100  inline float getCurrentCut() const
101  {
102  return mCurrentCut;
103  }
104 
105  inline void advanceToNextCut()
106  {
109  }
110 
111 protected:
112  int mMaxY;
115  float mCurrentCut;
116 };
117 
119 {
120  constexpr float epsilon = 0.001;
121  const auto diffy = std::round(point.y() - 0.5) - (point.y() - 0.5);
122  if (std::abs(diffy) < epsilon)
123  point.y() += diffy - std::copysign(epsilon, diffy);
124 
125  return point;
126 }
127 
128 inline void processEdge(const Point2f& current, const Point2f& prev, std::vector<EdgeCuts>& cuts)
129 {
130  if (prev.y() != current.y()) {
131  auto edge = EdgeCuts(current, prev);
132  if (edge.hasCuts()) {
133  cuts.push_back(std::move(edge));
134  }
135  }
136 }
137 
138 template<class Transformation>
139 std::vector<EdgeCuts> createEdgeList(const Polygon2f& polygon, Transformation&& F)
140 {
141  assert(polygon.size() > 1);
142 
143  std::vector<EdgeCuts> cuts;
144  cuts.reserve(polygon.size());
145 
146  const Point2f lastPoint = roundAwayFromGrid(F(polygon.back()));
147  Point2f prevPoint = lastPoint;
148  for (auto it = polygon.cbegin(); std::next(it) != polygon.cend(); ++it) {
149  const Point2f currentPoint = roundAwayFromGrid(F(*it));
150 
151  processEdge(currentPoint, prevPoint, cuts);
152  prevPoint = currentPoint;
153  }
154 
155  // in the final "iteration", just use the previously calculated lastPoint
156  // -> saving extra computation of F
157  processEdge(lastPoint, prevPoint, cuts);
158 
159  std::sort(cuts.begin(), cuts.end(),
160  [](const EdgeCuts& a, const EdgeCuts& b) { return a.getMaxY() > b.getMaxY(); });
161 
162  return cuts;
163 }
164 
166 {
167  using iterator = std::vector<EdgeCuts>::iterator;
168  using reverse_iterator = std::reverse_iterator<iterator>;
169 
171  {
172  begin = first;
173  end = std::next(begin, 2);
174  currentY = first->getMaxY();
175  }
176 
178  {
179  return reverse_iterator(end);
180  }
181 
183  {
184  return reverse_iterator(begin);
185  }
186 
187  int currentY;
190 };
191 
192 struct Interval
193 {
194  float start;
195  float end;
196 };
197 
198 inline bool intervalsOverlap(const Interval& interval1, const Interval& interval2)
199 {
200  assert(interval1.end >= interval1.start);
201  assert(interval2.end >= interval2.start);
202 
203  return !(interval2.end < interval1.start || interval2.start > interval1.end);
204 }
205 
207 {
208 public:
209  void reserve(std::size_t size)
210  {
211  mIntervals.reserve(size);
212  }
213 
214  void clear()
215  {
216  mIntervals.clear();
217  }
218 
219  bool empty() const
220  {
221  return mIntervals.empty();
222  }
223 
224  void addOrMerge(Interval interval)
225  {
226  // sort all overlapping intervals to end of container
227  const auto it = std::remove_if(mIntervals.begin(), mIntervals.end(), [&](const Interval& tInterval) {
228  const auto overlaps = intervalsOverlap(tInterval, interval);
229  if (overlaps) {
230  interval.start = std::min(interval.start, tInterval.start);
231  interval.end = std::max(interval.end, tInterval.end);
232  }
233  return overlaps;
234  });
235 
236  // erase overlapping intervals
237  mIntervals.erase(it, mIntervals.end());
238  // insert interval
239  mIntervals.push_back(std::move(interval));
240  }
241 
242  const std::vector<Interval>& getIntervals() const
243  {
244  return mIntervals;
245  }
246 
247 private:
248  std::vector<Interval> mIntervals;
249 };
250 
251 inline int scaleDown(int numToRound, int multiple)
252 {
253  int isNegative = (int)(numToRound < 0);
254  return ((numToRound - isNegative * (multiple - 1)) / multiple);
255 }
256 
257 inline bool compareCurrentCut(const EdgeCuts& a, const EdgeCuts& b)
258 {
259  return a.getCurrentCut() < b.getCurrentCut();
260 }
261 
263 inline void removeEmptyEdges(ActiveEdgeCuts& activeEdges)
264 {
265  auto it = std::remove_if(activeEdges.rbegin(), activeEdges.rend(), [](EdgeCuts& a) {
266  return !a.hasCuts();
267  });
268  activeEdges.begin = it.base();
269 }
270 
275 inline void advanceEdgeCuts(ActiveEdgeCuts& activeEdges)
276 {
277  // the standard requires that the predicate is called exactly once for every element
278  auto it = std::remove_if(activeEdges.rbegin(), activeEdges.rend(), [](EdgeCuts& a) {
279  a.advanceToNextCut();
280  return !a.hasCuts();
281  });
282  activeEdges.begin = it.base();
283  --activeEdges.currentY;
284 }
285 
286 template<class Visitor>
287 bool visitInterval(int x_start, int x_end, int y, Visitor& visitor)
288 {
289  for (int x = x_start; x <= x_end; ++x) {
290  if (visitor(x, y))
291  return true;
292  }
293  return false;
294 }
295 
297 
298 }} // namespace mira::Private
299 
300 #endif
Definition: RasterPolygonUtils.h:165
float mCurrentCut
Definition: RasterPolygonUtils.h:115
void processEdge(const Point2f &current, const Point2f &prev, std::vector< EdgeCuts > &cuts)
Definition: RasterPolygonUtils.h:128
Point2f roundAwayFromGrid(Point2f point)
Definition: RasterPolygonUtils.h:118
bool empty() const
Definition: RasterPolygonUtils.h:219
void clear()
Definition: RasterPolygonUtils.h:214
specialize cv::DataType for our ImgPixel and inherit from cv::DataType<Vec>
Definition: IOService.h:67
void advanceEdgeCuts(ActiveEdgeCuts &activeEdges)
advance edge cuts, move empty edges to front of container (and continue behind them) ...
Definition: RasterPolygonUtils.h:275
void removeEmptyEdges(ActiveEdgeCuts &activeEdges)
move empty edges to front of container (and continue behind them)
Definition: RasterPolygonUtils.h:263
int getMaxY() const
Definition: RasterPolygonUtils.h:85
bool visitInterval(int x_start, int x_end, int y, Visitor &visitor)
Definition: RasterPolygonUtils.h:287
int scaleDown(int numToRound, int multiple)
Definition: RasterPolygonUtils.h:251
std::vector< EdgeCuts >::iterator iterator
Definition: RasterPolygonUtils.h:167
bool compareCurrentCut(const EdgeCuts &a, const EdgeCuts &b)
Definition: RasterPolygonUtils.h:257
ActiveEdgeCuts(iterator first)
Definition: RasterPolygonUtils.h:170
bool intervalsOverlap(const Interval &interval1, const Interval &interval2)
Definition: RasterPolygonUtils.h:198
const std::vector< Interval > & getIntervals() const
Definition: RasterPolygonUtils.h:242
bool hasCuts() const
Definition: RasterPolygonUtils.h:95
Definition: RasterPolygonUtils.h:206
int mNumberOfCutsWithGrid
Definition: RasterPolygonUtils.h:113
Definition: RasterPolygonUtils.h:192
Simple Wrapper for Boost::geometry polygon.
reverse_iterator rbegin()
Definition: RasterPolygonUtils.h:177
iterator begin
Definition: RasterPolygonUtils.h:188
float getCurrentCut() const
Definition: RasterPolygonUtils.h:100
float start
Definition: RasterPolygonUtils.h:194
EdgeCuts(Point2f start, Point2f end)
Definition: RasterPolygonUtils.h:61
int currentY
Definition: RasterPolygonUtils.h:187
std::vector< EdgeCuts > createEdgeList(const Polygon2f &polygon, Transformation &&F)
Definition: RasterPolygonUtils.h:139
float mDeltaToNextCut
Definition: RasterPolygonUtils.h:114
reverse_iterator rend()
Definition: RasterPolygonUtils.h:182
iterator end
Definition: RasterPolygonUtils.h:189
void addOrMerge(Interval interval)
Definition: RasterPolygonUtils.h:224
Definition: RasterPolygonUtils.h:57
boost::geometry::model::ring< Point2f > Polygon2f
A 2D polygon with 32 bit floating precision.
Definition: Polygon.h:131
float end
Definition: RasterPolygonUtils.h:195
void advanceToNextCut()
Definition: RasterPolygonUtils.h:105
void reserve(std::size_t size)
Definition: RasterPolygonUtils.h:209
int mMaxY
Definition: RasterPolygonUtils.h:112
int getNumberOfCutsWithGrid() const
Definition: RasterPolygonUtils.h:90
std::reverse_iterator< iterator > reverse_iterator
Definition: RasterPolygonUtils.h:168