• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "separate_rects.h"
18 #include <algorithm>
19 #include <assert.h>
20 #include <iostream>
21 #include <map>
22 #include <set>
23 #include <utility>
24 #include <vector>
25 
26 namespace separate_rects {
27 
28 enum EventType { START, END };
29 
30 template <typename TId, typename TNum>
31 struct StartedRect {
32   IdSet<TId> id_set;
33   TNum left, top, bottom;
34 
35   // Note that this->left is not part of the key. That field is only to mark the
36   // left edge of the rectangle.
operator <separate_rects::StartedRect37   bool operator<(const StartedRect<TId, TNum> &rhs) const {
38     return (top < rhs.top || (top == rhs.top && bottom < rhs.bottom)) ||
39            (top == rhs.top && bottom == rhs.bottom && id_set < rhs.id_set);
40   }
41 };
42 
43 template <typename TId, typename TNum>
44 struct SweepEvent {
45   EventType type;
46   union {
47     TNum x;
48     TNum y;
49   };
50 
51   TId rect_id;
52 
operator <separate_rects::SweepEvent53   bool operator<(const SweepEvent<TId, TNum> &rhs) const {
54     return (y < rhs.y || (y == rhs.y && rect_id < rhs.rect_id));
55   }
56 };
57 
58 template <typename TNum>
operator <<(std::ostream & os,const Rect<TNum> & rect)59 std::ostream &operator<<(std::ostream &os, const Rect<TNum> &rect) {
60   return os << rect.bounds[0] << ", " << rect.bounds[1] << ", "
61             << rect.bounds[2] << ", " << rect.bounds[3];
62 }
63 
64 template <typename TUInt>
operator <<(std::ostream & os,const IdSet<TUInt> & obj)65 std::ostream &operator<<(std::ostream &os, const IdSet<TUInt> &obj) {
66   int bits = IdSet<TUInt>::max_elements;
67   TUInt mask = ((TUInt)0x1) << (bits - 1);
68   for (int i = 0; i < bits; i++)
69     os << ((obj.getBits() & (mask >> i)) ? "1" : "0");
70   return os;
71 }
72 
73 template <typename TNum, typename TId>
separate_rects(const std::vector<Rect<TNum>> & in,std::vector<RectSet<TId,TNum>> * out)74 void separate_rects(const std::vector<Rect<TNum>> &in,
75                     std::vector<RectSet<TId, TNum>> *out) {
76   // Overview:
77   // This algorithm is a line sweep algorithm that travels from left to right.
78   // The sweep stops at each vertical edge of each input rectangle in sorted
79   // order of x-coordinate. At each stop, the sweep line is examined in order of
80   // y-coordinate from top to bottom. Along the way, a running set of rectangle
81   // IDs is either added to or subtracted from as the top and bottom edges are
82   // encountered, respectively. At each change of that running set, a copy of
83   // that set is recorded in along with the the y-coordinate it happened at in a
84   // list. This list is then interpreted as a sort of vertical cross section of
85   // our output set of non-overlapping rectangles. Based of the algorithm found
86   // at: http://stackoverflow.com/a/2755498
87 
88   if (in.size() > IdSet<TId>::max_elements) {
89     return;
90   }
91 
92   // Events are when the sweep line encounters the starting or ending edge of
93   // any input rectangle.
94   std::set<SweepEvent<TId, TNum>> sweep_h_events;  // Left or right bounds
95   std::set<SweepEvent<TId, TNum>> sweep_v_events;  // Top or bottom bounds
96 
97   // A started rect is a rectangle whose left, top, bottom edge, and set of
98   // rectangle IDs is known. The key of this map includes all that information
99   // (except the left edge is never used to determine key equivalence or
100   // ordering),
101   std::map<StartedRect<TId, TNum>, bool> started_rects;
102 
103   // This is cleared after every event. Its declaration is here to avoid
104   // reallocating a vector and its buffers every event.
105   std::vector<std::pair<TNum, IdSet<TId>>> active_regions;
106 
107   // This pass will add rectangle start and end events to be triggered as the
108   // algorithm sweeps from left to right.
109   for (TId i = 0; i < in.size(); i++) {
110     const Rect<TNum> &rect = in[i];
111 
112     // Filter out empty or invalid rects.
113     if (rect.left >= rect.right || rect.top >= rect.bottom)
114       continue;
115 
116     SweepEvent<TId, TNum> evt;
117     evt.rect_id = i;
118 
119     evt.type = START;
120     evt.x = rect.left;
121     sweep_h_events.insert(evt);
122 
123     evt.type = END;
124     evt.x = rect.right;
125     sweep_h_events.insert(evt);
126   }
127 
128   for (typename std::set<SweepEvent<TId, TNum>>::iterator it =
129            sweep_h_events.begin();
130        it != sweep_h_events.end(); ++it) {
131     const SweepEvent<TId, TNum> &h_evt = *it;
132     const Rect<TNum> &rect = in[h_evt.rect_id];
133 
134     // During this event, we have encountered a vertical starting or ending edge
135     // of a rectangle so want to append or remove (respectively) that rectangles
136     // top and bottom from the vertical sweep line.
137     SweepEvent<TId, TNum> v_evt;
138     v_evt.rect_id = h_evt.rect_id;
139     if (h_evt.type == START) {
140       v_evt.type = START;
141       v_evt.y = rect.top;
142       sweep_v_events.insert(v_evt);
143 
144       v_evt.type = END;
145       v_evt.y = rect.bottom;
146       sweep_v_events.insert(v_evt);
147     } else {
148       v_evt.type = START;
149       v_evt.y = rect.top;
150       typename std::set<SweepEvent<TId, TNum>>::iterator start_it =
151           sweep_v_events.find(v_evt);
152       assert(start_it != sweep_v_events.end());
153       sweep_v_events.erase(start_it);
154 
155       v_evt.type = END;
156       v_evt.y = rect.bottom;
157       typename std::set<SweepEvent<TId, TNum>>::iterator end_it =
158           sweep_v_events.find(v_evt);
159       assert(end_it != sweep_v_events.end());
160       sweep_v_events.erase(end_it);
161     }
162 
163     // Peeks ahead to see if there are other rectangles sharing a vertical edge
164     // with the current sweep line. If so, we want to continue marking up the
165     // sweep line before actually processing the rectangles the sweep line is
166     // intersecting.
167     typename std::set<SweepEvent<TId, TNum>>::iterator next_it = it;
168     ++next_it;
169     if (next_it != sweep_h_events.end()) {
170       if (next_it->x == h_evt.x) {
171         continue;
172       }
173     }
174 
175 #ifdef RECTS_DEBUG
176     std::cout << h_evt.x << std::endl;
177 #endif
178 
179     // After the following for loop, active_regions will be a list of
180     // y-coordinates paired with the set of rectangle IDs that are intersect at
181     // that y-coordinate (and the current sweep line's x-coordinate). For
182     // example if the current sweep line were the left edge of a scene with only
183     // one rectangle of ID 0 and bounds (left, top, right, bottom) == (2, 3, 4,
184     // 5), active_regions will be [({ 0 }, 3), {}, 5].
185     active_regions.clear();
186     IdSet<TId> active_set;
187     for (typename std::set<SweepEvent<TId, TNum>>::iterator it =
188              sweep_v_events.begin();
189          it != sweep_v_events.end(); ++it) {
190       const SweepEvent<TId, TNum> &v_evt = *it;
191 
192       if (v_evt.type == START) {
193         active_set.add(v_evt.rect_id);
194       } else {
195         active_set.subtract(v_evt.rect_id);
196       }
197 
198       if (active_regions.size() > 0 && active_regions.back().first == v_evt.y) {
199         active_regions.back().second = active_set;
200       } else {
201         active_regions.push_back(std::make_pair(v_evt.y, active_set));
202       }
203     }
204 
205 #ifdef RECTS_DEBUG
206     std::cout << "x:" << h_evt.x;
207     for (std::vector<std::pair<TNum, IdSet>>::iterator it =
208              active_regions.begin();
209          it != active_regions.end(); ++it) {
210       std::cout << " " << it->first << "(" << it->second << ")"
211                 << ",";
212     }
213     std::cout << std::endl;
214 #endif
215 
216     // To determine which started rectangles are ending this event, we make them
217     // all as false, or unseen during this sweep line.
218     for (typename std::map<StartedRect<TId, TNum>, bool>::iterator it =
219              started_rects.begin();
220          it != started_rects.end(); ++it) {
221       it->second = false;
222     }
223 
224     // This for loop will iterate all potential new rectangles and either
225     // discover it was already started (and then mark it true), or that it is a
226     // new rectangle and add it to the started rectangles. A started rectangle
227     // is unique if it has a distinct top, bottom, and set of rectangle IDs.
228     // This is tricky because a potential rectangle could be encountered here
229     // that has a non-unique top and bottom, so it shares geometry with an
230     // already started rectangle, but the set of rectangle IDs differs. In that
231     // case, we have a new rectangle, and the already existing started rectangle
232     // will not be marked as seen ("true" in the std::pair) and will get ended
233     // by the for loop after this one. This is as intended.
234     for (typename std::vector<std::pair<TNum, IdSet<TId>>>::iterator it =
235              active_regions.begin();
236          it != active_regions.end(); ++it) {
237       IdSet<TId> region_set = it->second;
238 
239       if (region_set.isEmpty())
240         continue;
241 
242       // An important property of active_regions is that each region where a set
243       // of rectangles applies is bounded at the bottom by the next (in the
244       // vector) region's starting y-coordinate.
245       typename std::vector<std::pair<TNum, IdSet<TId>>>::iterator next_it = it;
246       ++next_it;
247       assert(next_it != active_regions.end());
248 
249       TNum region_top = it->first;
250       TNum region_bottom = next_it->first;
251 
252       StartedRect<TId, TNum> rect_key;
253       rect_key.id_set = region_set;
254       rect_key.left = h_evt.x;
255       rect_key.top = region_top;
256       rect_key.bottom = region_bottom;
257 
258       // Remember that rect_key.left is ignored for the purposes of searching
259       // the started rects. This follows from the fact that a previously started
260       // rectangle would by definition have a left bound less than the current
261       // event's x-coordinate. We are interested in continuing the started
262       // rectangles by marking them seen (true) but we don't know, care, or wish
263       // to change the left bound at this point. If there are no matching
264       // rectangles for this region, start a new one and mark it as seen (true).
265       typename std::map<StartedRect<TId, TNum>, bool>::iterator
266           started_rect_it = started_rects.find(rect_key);
267       if (started_rect_it == started_rects.end()) {
268         started_rects[rect_key] = true;
269       } else {
270         started_rect_it->second = true;
271       }
272     }
273 
274     // This for loop ends all rectangles that were unseen during this event.
275     // Because this is the first event where we didn't see this rectangle, it's
276     // right edge is exactly the current event's x-coordinate. With this, we
277     // have the final piece of information to output this rectangle's geometry
278     // and set of input rectangle IDs. To end a started rectangle, we erase it
279     // from the started_rects map and append the completed rectangle to the
280     // output vector.
281     for (typename std::map<StartedRect<TId, TNum>, bool>::iterator it =
282              started_rects.begin();
283          it != started_rects.end();
284          /* inc in body */) {
285       if (!it->second) {
286         const StartedRect<TId, TNum> &proto_rect = it->first;
287         Rect<TNum> out_rect;
288         out_rect.left = proto_rect.left;
289         out_rect.top = proto_rect.top;
290         out_rect.right = h_evt.x;
291         out_rect.bottom = proto_rect.bottom;
292         out->push_back(RectSet<TId, TNum>(proto_rect.id_set, out_rect));
293         started_rects.erase(it++);  // Also increments out iterator.
294 
295 #ifdef RECTS_DEBUG
296         std::cout << "    <" << proto_rect.id_set << "(" << rect << ")"
297                   << std::endl;
298 #endif
299       } else {
300         // Remember this for loop has no built in increment step. We do it here.
301         ++it;
302       }
303     }
304   }
305 }
306 
separate_frects_64(const std::vector<Rect<float>> & in,std::vector<RectSet<uint64_t,float>> * out)307 void separate_frects_64(const std::vector<Rect<float>> &in,
308                         std::vector<RectSet<uint64_t, float>> *out) {
309   separate_rects(in, out);
310 }
311 
separate_rects_64(const std::vector<Rect<int>> & in,std::vector<RectSet<uint64_t,int>> * out)312 void separate_rects_64(const std::vector<Rect<int>> &in,
313                        std::vector<RectSet<uint64_t, int>> *out) {
314   separate_rects(in, out);
315 }
316 
317 }  // namespace separate_rects
318 
319 #ifdef RECTS_TEST
320 
321 using namespace separate_rects;
322 
main(int argc,char ** argv)323 int main(int argc, char **argv) {
324 #define RectSet RectSet<TId, TNum>
325 #define Rect Rect<TNum>
326 #define IdSet IdSet<TId>
327   typedef uint64_t TId;
328   typedef float TNum;
329 
330   std::vector<Rect> in;
331   std::vector<RectSet> out;
332   std::vector<RectSet> expected_out;
333 
334   in.push_back({0, 0, 4, 5});
335   in.push_back({2, 0, 6, 6});
336   in.push_back({4, 0, 8, 5});
337   in.push_back({0, 7, 8, 9});
338 
339   in.push_back({10, 0, 18, 5});
340   in.push_back({12, 0, 16, 5});
341 
342   in.push_back({20, 11, 24, 17});
343   in.push_back({22, 13, 26, 21});
344   in.push_back({32, 33, 36, 37});
345   in.push_back({30, 31, 38, 39});
346 
347   in.push_back({40, 43, 48, 45});
348   in.push_back({44, 41, 46, 47});
349 
350   in.push_back({50, 51, 52, 53});
351   in.push_back({50, 51, 52, 53});
352   in.push_back({50, 51, 52, 53});
353 
354   in.push_back({0, 0, 0, 10});
355   in.push_back({0, 0, 10, 0});
356   in.push_back({10, 0, 0, 10});
357   in.push_back({0, 10, 10, 0});
358 
359   for (int i = 0; i < 100000; i++) {
360     out.clear();
361     separate_rects(in, &out);
362   }
363 
364   for (int i = 0; i < out.size(); i++) {
365     std::cout << out[i].id_set << "(" << out[i].rect << ")" << std::endl;
366   }
367 
368   std::cout << "# of rects: " << out.size() << std::endl;
369 
370   expected_out.push_back(RectSet(IdSet(0), Rect(0, 0, 2, 5)));
371   expected_out.push_back(RectSet(IdSet(1), Rect(2, 5, 6, 6)));
372   expected_out.push_back(RectSet(IdSet(1) | 0, Rect(2, 0, 4, 5)));
373   expected_out.push_back(RectSet(IdSet(1) | 2, Rect(4, 0, 6, 5)));
374   expected_out.push_back(RectSet(IdSet(2), Rect(6, 0, 8, 5)));
375   expected_out.push_back(RectSet(IdSet(3), Rect(0, 7, 8, 9)));
376   expected_out.push_back(RectSet(IdSet(4), Rect(10, 0, 12, 5)));
377   expected_out.push_back(RectSet(IdSet(5) | 4, Rect(12, 0, 16, 5)));
378   expected_out.push_back(RectSet(IdSet(4), Rect(16, 0, 18, 5)));
379   expected_out.push_back(RectSet(IdSet(6), Rect(20, 11, 22, 17)));
380   expected_out.push_back(RectSet(IdSet(6) | 7, Rect(22, 13, 24, 17)));
381   expected_out.push_back(RectSet(IdSet(6), Rect(22, 11, 24, 13)));
382   expected_out.push_back(RectSet(IdSet(7), Rect(22, 17, 24, 21)));
383   expected_out.push_back(RectSet(IdSet(7), Rect(24, 13, 26, 21)));
384   expected_out.push_back(RectSet(IdSet(9), Rect(30, 31, 32, 39)));
385   expected_out.push_back(RectSet(IdSet(8) | 9, Rect(32, 33, 36, 37)));
386   expected_out.push_back(RectSet(IdSet(9), Rect(32, 37, 36, 39)));
387   expected_out.push_back(RectSet(IdSet(9), Rect(32, 31, 36, 33)));
388   expected_out.push_back(RectSet(IdSet(9), Rect(36, 31, 38, 39)));
389   expected_out.push_back(RectSet(IdSet(10), Rect(40, 43, 44, 45)));
390   expected_out.push_back(RectSet(IdSet(10) | 11, Rect(44, 43, 46, 45)));
391   expected_out.push_back(RectSet(IdSet(11), Rect(44, 41, 46, 43)));
392   expected_out.push_back(RectSet(IdSet(11), Rect(44, 45, 46, 47)));
393   expected_out.push_back(RectSet(IdSet(10), Rect(46, 43, 48, 45)));
394   expected_out.push_back(RectSet(IdSet(12) | 13 | 14, Rect(50, 51, 52, 53)));
395 
396   for (int i = 0; i < expected_out.size(); i++) {
397     RectSet &ex_out = expected_out[i];
398     if (std::find(out.begin(), out.end(), ex_out) == out.end()) {
399       std::cout << "Missing Rect: " << ex_out.id_set << "(" << ex_out.rect
400                 << ")" << std::endl;
401     }
402   }
403 
404   for (int i = 0; i < out.size(); i++) {
405     RectSet &actual_out = out[i];
406     if (std::find(expected_out.begin(), expected_out.end(), actual_out) ==
407         expected_out.end()) {
408       std::cout << "Extra Rect: " << actual_out.id_set << "(" << actual_out.rect
409                 << ")" << std::endl;
410     }
411   }
412 
413   return 0;
414 }
415 
416 #endif
417