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<TNum>::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