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. 37 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 53 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> 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> 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> 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 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 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 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
