MIRA
RasterPolygon.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_RASTERPOLYGON_H_
48 #define _MIRA_BASE_INCLUDE_GEOMETRY_RASTERPOLYGON_H_
49 
51 #include <geometry/Rect.h>
52 
53 namespace mira {
54 
56 
57 namespace Private {
58 
60 
65 template<class Visitor>
66 bool processActiveEdges(ActiveEdgeCuts& activeEdges, const Rect2i& region, Visitor& visitor)
67 {
68  // even-odd rule ensures every complete horizontal cut has an even number of points
69  assert(activeEdges.begin <= activeEdges.end);
70  assert(std::distance(activeEdges.begin, activeEdges.end) % 2 == 0);
71 
72  // sort active edges by their current x (x for y)
73  std::sort(activeEdges.begin, activeEdges.end, &Private::compareCurrentCut);
74 
75  if (region.y0() <= activeEdges.currentY && activeEdges.currentY < region.y1()) {
76  for (auto it = activeEdges.begin; it != activeEdges.end; std::advance(it, 2)) {
77  const auto x_start = std::max(region.x0(),
78  (int)std::floor(it->getCurrentCut()));
79  const auto x_end = std::min(region.x1() - 1,
80  (int)std::floor(std::next(it)->getCurrentCut()));
81 
82  if (visitInterval(x_start, x_end, activeEdges.currentY, visitor)) {
83  return true;
84  }
85  }
86  }
87 
88  advanceEdgeCuts(activeEdges);
89  return false;
90 }
91 
97 template<class Visitor>
98 bool processTwoActiveEdges(ActiveEdgeCuts& activeEdges, const Rect2i& region,
99  Visitor& visitor, const int nextY)
100 {
101  assert(std::distance(activeEdges.begin, activeEdges.end) == 2);
102 
103  auto& firstEdge = *activeEdges.begin;
104  auto& secondEdge = *std::next(activeEdges.begin);
105  while (activeEdges.currentY > nextY) {
106  if (region.y0() <= activeEdges.currentY && activeEdges.currentY < region.y1()) {
107  auto cut1 = (int)std::floor(firstEdge.getCurrentCut());
108  auto cut2 = (int)std::floor(secondEdge.getCurrentCut());
109 
110  if (cut1 > cut2)
111  std::swap(cut1, cut2);
112 
113  const auto x_start = std::max(region.x0(), cut1);
114  const auto x_end = std::min(region.x1() - 1, cut2);
115 
116  if (visitInterval(x_start, x_end, activeEdges.currentY, visitor)) {
117  return true;
118  }
119  }
120 
121  firstEdge.advanceToNextCut();
122  secondEdge.advanceToNextCut();
123  --activeEdges.currentY;
124  }
125 
126  removeEmptyEdges(activeEdges);
127 
128  return false;
129 }
130 
131 template<class Visitor>
132 bool processIntervals(const ActiveEdgeCuts& activeEdges, Intervals& intervals, const Rect2i& region,
133  Visitor& visitor, uint precision)
134 {
135  if (activeEdges.currentY % precision == 0) {
136  const int y_inGrid_coordinates = activeEdges.currentY / (int)precision;
137 
138  if (region.y0() <= y_inGrid_coordinates && y_inGrid_coordinates < region.y1()) {
139  for (const auto& interval : intervals.getIntervals()) {
140  const auto x_start = std::max(region.x0(),
141  scaleDown(std::floor(interval.start), precision));
142  const auto x_end = std::min(region.x1() - 1,
143  scaleDown(std::floor(interval.end), precision));
144 
145  if (visitInterval(x_start, x_end, y_inGrid_coordinates, visitor)) {
146  return true;
147  }
148  }
149  }
150  intervals.clear();
151  }
152 
153  return false;
154 }
155 
157 template<class Visitor>
158 bool processActiveEdges(ActiveEdgeCuts& activeEdges, Intervals& intervals, const Rect2i& region,
159  Visitor& visitor, uint precision)
160 {
161  // even-odd rule ensures every complete horizontal cut has an even number of points
162  assert(activeEdges.begin <= activeEdges.end);
163  assert(std::distance(activeEdges.begin, activeEdges.end) % 2 == 0);
164 
165  // sort active edges by their current x (x for y)
166  std::sort(activeEdges.begin, activeEdges.end, &Private::compareCurrentCut);
167 
168  for (auto it = activeEdges.begin; it != activeEdges.end; std::advance(it, 2)) {
169  intervals.addOrMerge({it->getCurrentCut(), std::next(it)->getCurrentCut()});
170  }
171 
172  if (processIntervals(activeEdges, intervals, region, visitor, precision)) {
173  return true;
174  }
175 
176  advanceEdgeCuts(activeEdges);
177  return false;
178 }
179 
181 template<class Visitor>
182 bool processTwoActiveEdges(ActiveEdgeCuts& activeEdges, Intervals& intervals, const Rect2i& region,
183  Visitor& visitor, const uint precision, const int nextY)
184 {
185  assert(std::distance(activeEdges.begin, activeEdges.end) == 2);
186 
187  auto& firstEdge = *activeEdges.begin;
188  auto& secondEdge = *std::next(activeEdges.begin);
189  while (activeEdges.currentY > nextY) {
190  auto cut1 = std::floor(firstEdge.getCurrentCut());
191  auto cut2 = std::floor(secondEdge.getCurrentCut());
192 
193  if(cut1 > cut2)
194  std::swap(cut1, cut2);
195 
196  intervals.addOrMerge({cut1, cut2});
197 
198  if (processIntervals(activeEdges, intervals, region, visitor, precision)) {
199  return true;
200  }
201 
202  firstEdge.advanceToNextCut();
203  secondEdge.advanceToNextCut();
204  --activeEdges.currentY;
205  }
206 
207  removeEmptyEdges(activeEdges);
208 
209  return false;
210 }
211 
213 
214 } // namespace Private
215 
231 template<class TransformationInRegion, class Visitor>
232 void rasterPolygon(const Polygon2f& polygon, const Rect2i& region,
233  TransformationInRegion&& transformation, Visitor&& visitor)
234 {
235  if (polygon.size() <= 2)
236  return;
237 
238  if (!region.isValid())
239  return;
240 
241  auto edgeList = Private::createEdgeList(polygon,
242  std::forward<TransformationInRegion>(transformation));
243 
244  if (edgeList.empty())
245  return;
246 
247  assert(edgeList.size() >= 2);
248  auto activeEdges = Private::ActiveEdgeCuts(edgeList.begin());
249 
250  for (; activeEdges.end != edgeList.end(); ++activeEdges.end) {
251  while (activeEdges.currentY > activeEdges.end->getMaxY()) {
252  // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
253  if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
254  if (processTwoActiveEdges(activeEdges, region, visitor, activeEdges.end->getMaxY())) {
255  return;
256  }
257  }
258  else if (processActiveEdges(activeEdges, region, visitor)) {
259  return;
260  }
261  }
262  }
263 
264  while (activeEdges.begin != activeEdges.end) {
265  // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
266  if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
267  const auto yEnd = activeEdges.currentY - activeEdges.begin->getNumberOfCutsWithGrid();
268  if (processTwoActiveEdges(activeEdges, region, visitor, yEnd)) {
269  return;
270  }
271  }
272  else if (processActiveEdges(activeEdges, region, visitor)) {
273  return;
274  }
275  }
276 }
277 
279 
296 template<class TransformationInRegion, class Visitor>
297 void rasterPolygon(const Polygon2f& polygon, const Rect2i& region,
298  TransformationInRegion&& transformation, Visitor&& visitor, uint precision)
299 {
300  // without precision, just call plain rasterPolygon()
301  if (precision <= 1) {
302  rasterPolygon(polygon, region, std::forward<TransformationInRegion>(transformation),
303  std::forward<Visitor>(visitor));
304  return;
305  }
306 
307  if (polygon.size() <= 2)
308  return;
309 
310  if (!region.isValid())
311  return;
312 
313  auto edgeList = Private::createEdgeList(polygon, [&](const Point2f& p) {
314  const Point2f p_transformed = transformation(p) * (float)precision;
315  return p_transformed;
316  });
317 
318  if (edgeList.empty())
319  return;
320 
321  assert(edgeList.size() >= 2);
322  auto activeEdges = Private::ActiveEdgeCuts(edgeList.begin());
323 
324  Private::Intervals intervals;
325 
326  for (; activeEdges.end != edgeList.end(); ++activeEdges.end) {
327  while (activeEdges.currentY > activeEdges.end->getMaxY()) {
328  // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
329  if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
330  if (processTwoActiveEdges(activeEdges, intervals, region, visitor, precision,
331  activeEdges.end->getMaxY())) {
332  return;
333  }
334  }
335  else if (processActiveEdges(activeEdges, intervals, region, visitor, precision)) {
336  return;
337  }
338  }
339  }
340 
341  while (activeEdges.begin != activeEdges.end || !intervals.empty()) {
342  // the case with two edges can be handled more efficiently and is quite common (any convex polygon)
343  if (std::distance(activeEdges.begin, activeEdges.end) == 2) {
344  const auto yEnd = activeEdges.currentY - activeEdges.begin->getNumberOfCutsWithGrid();
345  if (processTwoActiveEdges(activeEdges, intervals, region, visitor, precision, yEnd)) {
346  return;
347  }
348  }
349  else if (processActiveEdges(activeEdges, intervals, region, visitor, precision)) {
350  return;
351  }
352  }
353 }
354 
356 
357 } // namespace mira
358 
359 #endif
Definition: RasterPolygonUtils.h:165
void rasterPolygon(const Polygon2f &polygon, const Rect2i &region, TransformationInRegion &&transformation, Visitor &&visitor)
Function for rasterising a polygon.
Definition: RasterPolygon.h:232
bool processActiveEdges(ActiveEdgeCuts &activeEdges, const Rect2i &region, Visitor &visitor)
Process all active edges at current y, advance y, remove any edges that are finished, then return.
Definition: RasterPolygon.h:66
void clear()
Definition: RasterPolygonUtils.h:214
Utilities for rasterPolygon.
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
bool processTwoActiveEdges(ActiveEdgeCuts &activeEdges, const Rect2i &region, Visitor &visitor, const int nextY)
Optimization of processActiveEdges() for exactly 2 active edges: None of them can finish before anoth...
Definition: RasterPolygon.h:98
bool visitInterval(int x_start, int x_end, int y, Visitor &visitor)
Definition: RasterPolygonUtils.h:287
bool isValid() const
Returns true if this is a valid Rect where the maxCorner&#39;s components are not smaller than the minCor...
Definition: Rect.h:213
int scaleDown(int numToRound, int multiple)
Definition: RasterPolygonUtils.h:251
bool processIntervals(const ActiveEdgeCuts &activeEdges, Intervals &intervals, const Rect2i &region, Visitor &visitor, uint precision)
Definition: RasterPolygon.h:132
bool compareCurrentCut(const EdgeCuts &a, const EdgeCuts &b)
Definition: RasterPolygonUtils.h:257
const std::vector< Interval > & getIntervals() const
Definition: RasterPolygonUtils.h:242
bool processActiveEdges(ActiveEdgeCuts &activeEdges, Intervals &intervals, const Rect2i &region, Visitor &visitor, uint precision)
See above.
Definition: RasterPolygon.h:158
Provides multidimensional rectangle templates.
Definition: RasterPolygonUtils.h:206
iterator begin
Definition: RasterPolygonUtils.h:188
int currentY
Definition: RasterPolygonUtils.h:187
std::vector< EdgeCuts > createEdgeList(const Polygon2f &polygon, Transformation &&F)
Definition: RasterPolygonUtils.h:139
bool processTwoActiveEdges(ActiveEdgeCuts &activeEdges, Intervals &intervals, const Rect2i &region, Visitor &visitor, const uint precision, const int nextY)
See above.
Definition: RasterPolygon.h:182
PropertyHint precision(int p)
Sets the attribute "precision".
Definition: PropertyHint.h:285
iterator end
Definition: RasterPolygonUtils.h:189
void addOrMerge(Interval interval)
Definition: RasterPolygonUtils.h:224
boost::geometry::model::ring< Point2f > Polygon2f
A 2D polygon with 32 bit floating precision.
Definition: Polygon.h:131