separate_rects.cpp

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