seperate_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 "seperate_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 seperate_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 seperate_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     SweepEvent<TId, TNum> evt;
 112     evt.rect_id = i;
 113
 114     evt.type = START;
 115     evt.x = rect.left;
 116     sweep_h_events.insert(evt);
 117
 118     evt.type = END;
 119     evt.x = rect.right;
 120     sweep_h_events.insert(evt);
 121   }
 122
 123   for (typename std::set<SweepEvent<TId, TNum> >::iterator it =
 124            sweep_h_events.begin();
 125        it != sweep_h_events.end(); ++it) {
 126     const SweepEvent<TId, TNum> &h_evt = *it;
 127     const Rect<TNum> &rect = in[h_evt.rect_id];
 128
 129     // During this event, we have encountered a vertical starting or ending edge
 130     // of a rectangle so want to append or remove (respectively) that rectangles
 131     // top and bottom from the vertical sweep line.
 132     SweepEvent<TId, TNum> v_evt;
 133     v_evt.rect_id = h_evt.rect_id;
 134     if (h_evt.type == START) {
 135       v_evt.type = START;
 136       v_evt.y = rect.top;
 137       sweep_v_events.insert(v_evt);
 138
 139       v_evt.type = END;
 140       v_evt.y = rect.bottom;
 141       sweep_v_events.insert(v_evt);
 142     } else {
 143       v_evt.type = START;
 144       v_evt.y = rect.top;
 145       typename std::set<SweepEvent<TId, TNum> >::iterator start_it =
 146           sweep_v_events.find(v_evt);
 147       assert(start_it != sweep_v_events.end());
 148       sweep_v_events.erase(start_it);
 149
 150       v_evt.type = END;
 151       v_evt.y = rect.bottom;
 152       typename std::set<SweepEvent<TId, TNum> >::iterator end_it =
 153           sweep_v_events.find(v_evt);
 154       assert(end_it != sweep_v_events.end());
 155       sweep_v_events.erase(end_it);
 156     }
 157
 158     // Peeks ahead to see if there are other rectangles sharing a vertical edge
 159     // with the current sweep line. If so, we want to continue marking up the
 160     // sweep line before actually processing the rectangles the sweep line is
 161     // intersecting.
 162     typename std::set<SweepEvent<TId, TNum> >::iterator next_it = it;
 163     ++next_it;
 164     if (next_it != sweep_h_events.end()) {
 165       if (next_it->x == h_evt.x) {
 166         continue;
 167       }
 168     }
 169
 170 #ifdef RECTS_DEBUG
 171     std::cout << h_evt.x << std::endl;
 172 #endif
 173
 174     // After the following for loop, active_regions will be a list of
 175     // y-coordinates paired with the set of rectangle IDs that are intersect at
 176     // that y-coordinate (and the current sweep line's x-coordinate). For
 177     // example if the current sweep line were the left edge of a scene with only
 178     // one rectangle of ID 0 and bounds (left, top, right, bottom) == (2, 3, 4,
 179     // 5), active_regions will be [({ 0 }, 3), {}, 5].
 180     active_regions.clear();
 181     IdSet<TId> active_set;
 182     for (typename std::set<SweepEvent<TId, TNum> >::iterator it =
 183              sweep_v_events.begin();
 184          it != sweep_v_events.end(); ++it) {
 185       const SweepEvent<TId, TNum> &v_evt = *it;
 186
 187       if (v_evt.type == START) {
 188         active_set.add(v_evt.rect_id);
 189       } else {
 190         active_set.subtract(v_evt.rect_id);
 191       }
 192
 193       if (active_regions.size() > 0 && active_regions.back().first == v_evt.y) {
 194         active_regions.back().second = active_set;
 195       } else {
 196         active_regions.push_back(std::make_pair(v_evt.y, active_set));
 197       }
 198     }
 199
 200 #ifdef RECTS_DEBUG
 201     std::cout << "x:" << h_evt.x;
 202     for (std::vector<std::pair<TNum, IdSet> >::iterator it =
 203              active_regions.begin();
 204          it != active_regions.end(); ++it) {
 205       std::cout << " " << it->first << "(" << it->second << ")"
 206                 << ",";
 207     }
 208     std::cout << std::endl;
 209 #endif
 210
 211     // To determine which started rectangles are ending this event, we make them
 212     // all as false, or unseen during this sweep line.
 213     for (typename std::map<StartedRect<TId, TNum>, bool>::iterator it =
 214              started_rects.begin();
 215          it != started_rects.end(); ++it) {
 216       it->second = false;
 217     }
 218
 219     // This for loop will iterate all potential new rectangles and either
 220     // discover it was already started (and then mark it true), or that it is a
 221     // new rectangle and add it to the started rectangles. A started rectangle
 222     // is unique if it has a distinct top, bottom, and set of rectangle IDs.
 223     // This is tricky because a potential rectangle could be encountered here
 224     // that has a non-unique top and bottom, so it shares geometry with an
 225     // already started rectangle, but the set of rectangle IDs differs. In that
 226     // case, we have a new rectangle, and the already existing started rectangle
 227     // will not be marked as seen ("true" in the std::pair) and will get ended
 228     // by the for loop after this one. This is as intended.
 229     for (typename std::vector<std::pair<TNum, IdSet<TId> > >::iterator it =
 230              active_regions.begin();
 231          it != active_regions.end(); ++it) {
 232       IdSet<TId> region_set = it->second;
 233
 234       if (region_set.isEmpty())
 235         continue;
 236
 237       // An important property of active_regions is that each region where a set
 238       // of rectangles applies is bounded at the bottom by the next (in the
 239       // vector) region's starting y-coordinate.
 240       typename std::vector<std::pair<TNum, IdSet<TId> > >::iterator next_it =
 241           it;
 242       ++next_it;
 243       assert(next_it != active_regions.end());
 244
 245       TNum region_top = it->first;
 246       TNum region_bottom = next_it->first;
 247
 248       StartedRect<TId, TNum> rect_key;
 249       rect_key.id_set = region_set;
 250       rect_key.left = h_evt.x;
 251       rect_key.top = region_top;
 252       rect_key.bottom = region_bottom;
 253
 254       // Remember that rect_key.left is ignored for the purposes of searching
 255       // the started rects. This follows from the fact that a previously started
 256       // rectangle would by definition have a left bound less than the current
 257       // event's x-coordinate. We are interested in continuing the started
 258       // rectangles by marking them seen (true) but we don't know, care, or wish
 259       // to change the left bound at this point. If there are no matching
 260       // rectangles for this region, start a new one and mark it as seen (true).
 261       typename std::map<StartedRect<TId, TNum>, bool>::iterator
 262           started_rect_it = started_rects.find(rect_key);
 263       if (started_rect_it == started_rects.end()) {
 264         started_rects[rect_key] = true;
 265       } else {
 266         started_rect_it->second = true;
 267       }
 268     }
 269
 270     // This for loop ends all rectangles that were unseen during this event.
 271     // Because this is the first event where we didn't see this rectangle, it's
 272     // right edge is exactly the current event's x-coordinate. With this, we
 273     // have the final piece of information to output this rectangle's geometry
 274     // and set of input rectangle IDs. To end a started rectangle, we erase it
 275     // from the started_rects map and append the completed rectangle to the
 276     // output vector.
 277     for (typename std::map<StartedRect<TId, TNum>, bool>::iterator it =
 278              started_rects.begin();
 279          it != started_rects.end();
 280          /* inc in body */) {
 281       if (!it->second) {
 282         const StartedRect<TId, TNum> &proto_rect = it->first;
 283         Rect<TNum> out_rect;
 284         out_rect.left = proto_rect.left;
 285         out_rect.top = proto_rect.top;
 286         out_rect.right = h_evt.x;
 287         out_rect.bottom = proto_rect.bottom;
 288         out->push_back(RectSet<TId, TNum>(proto_rect.id_set, out_rect));
 289         started_rects.erase(it++);  // Also increments out iterator.
 290
 291 #ifdef RECTS_DEBUG
 292         std::cout << "    <" << proto_rect.id_set << "(" << rect << ")"
 293                   << std::endl;
 294 #endif
 295       } else {
 296         // Remember this for loop has no built in increment step. We do it here.
 297         ++it;
 298       }
 299     }
 300   }
 301 }
 302
 303 void seperate_frects_64(const std::vector<Rect<float> > &in,
 304                         std::vector<RectSet<uint64_t, float> > *out) {
 305   seperate_rects(in, out);
 306 }
 307
 308 }  // namespace seperate_rects
 309
 310 #ifdef RECTS_TEST
 311
 312 using namespace seperate_rects;
 313
 314 int main(int argc, char **argv) {
 315 #define RectSet RectSet<TId, TNum>
 316 #define Rect Rect<TNum>
 317 #define IdSet IdSet<TId>
 318   typedef uint64_t TId;
 319   typedef float TNum;
 320
 321   std::vector<Rect> in;
 322   std::vector<RectSet> out;
 323   std::vector<RectSet> expected_out;
 324
 325   in.push_back({0, 0, 4, 5});
 326   in.push_back({2, 0, 6, 6});
 327   in.push_back({4, 0, 8, 5});
 328   in.push_back({0, 7, 8, 9});
 329
 330   in.push_back({10, 0, 18, 5});
 331   in.push_back({12, 0, 16, 5});
 332
 333   in.push_back({20, 11, 24, 17});
 334   in.push_back({22, 13, 26, 21});
 335   in.push_back({32, 33, 36, 37});
 336   in.push_back({30, 31, 38, 39});
 337
 338   in.push_back({40, 43, 48, 45});
 339   in.push_back({44, 41, 46, 47});
 340
 341   in.push_back({50, 51, 52, 53});
 342   in.push_back({50, 51, 52, 53});
 343   in.push_back({50, 51, 52, 53});
 344
 345   for (int i = 0; i < 100000; i++) {
 346     out.clear();
 347     seperate_rects(in, &out);
 348   }
 349
 350   for (int i = 0; i < out.size(); i++) {
 351     std::cout << out[i].id_set << "(" << out[i].rect << ")" << std::endl;
 352   }
 353
 354   std::cout << "# of rects: " << out.size() << std::endl;
 355
 356   expected_out.push_back(RectSet(IdSet(0), Rect(0, 0, 2, 5)));
 357   expected_out.push_back(RectSet(IdSet(1), Rect(2, 5, 6, 6)));
 358   expected_out.push_back(RectSet(IdSet(1) | 0, Rect(2, 0, 4, 5)));
 359   expected_out.push_back(RectSet(IdSet(1) | 2, Rect(4, 0, 6, 5)));
 360   expected_out.push_back(RectSet(IdSet(2), Rect(6, 0, 8, 5)));
 361   expected_out.push_back(RectSet(IdSet(3), Rect(0, 7, 8, 9)));
 362   expected_out.push_back(RectSet(IdSet(4), Rect(10, 0, 12, 5)));
 363   expected_out.push_back(RectSet(IdSet(5) | 4, Rect(12, 0, 16, 5)));
 364   expected_out.push_back(RectSet(IdSet(4), Rect(16, 0, 18, 5)));
 365   expected_out.push_back(RectSet(IdSet(6), Rect(20, 11, 22, 17)));
 366   expected_out.push_back(RectSet(IdSet(6) | 7, Rect(22, 13, 24, 17)));
 367   expected_out.push_back(RectSet(IdSet(6), Rect(22, 11, 24, 13)));
 368   expected_out.push_back(RectSet(IdSet(7), Rect(22, 17, 24, 21)));
 369   expected_out.push_back(RectSet(IdSet(7), Rect(24, 13, 26, 21)));
 370   expected_out.push_back(RectSet(IdSet(9), Rect(30, 31, 32, 39)));
 371   expected_out.push_back(RectSet(IdSet(8) | 9, Rect(32, 33, 36, 37)));
 372   expected_out.push_back(RectSet(IdSet(9), Rect(32, 37, 36, 39)));
 373   expected_out.push_back(RectSet(IdSet(9), Rect(32, 31, 36, 33)));
 374   expected_out.push_back(RectSet(IdSet(9), Rect(36, 31, 38, 39)));
 375   expected_out.push_back(RectSet(IdSet(10), Rect(40, 43, 44, 45)));
 376   expected_out.push_back(RectSet(IdSet(10) | 11, Rect(44, 43, 46, 45)));
 377   expected_out.push_back(RectSet(IdSet(11), Rect(44, 41, 46, 43)));
 378   expected_out.push_back(RectSet(IdSet(11), Rect(44, 45, 46, 47)));
 379   expected_out.push_back(RectSet(IdSet(10), Rect(46, 43, 48, 45)));
 380   expected_out.push_back(RectSet(IdSet(12) | 13 | 14, Rect(50, 51, 52, 53)));
 381
 382   for (int i = 0; i < expected_out.size(); i++) {
 383     RectSet &ex_out = expected_out[i];
 384     if (std::find(out.begin(), out.end(), ex_out) == out.end()) {
 385       std::cout << "Missing Rect: " << ex_out.id_set << "(" << ex_out.rect
 386                 << ")" << std::endl;
 387     }
 388   }
 389
 390   for (int i = 0; i < out.size(); i++) {
 391     RectSet &actual_out = out[i];
 392     if (std::find(expected_out.begin(), expected_out.end(), actual_out) ==
 393         expected_out.end()) {
 394       std::cout << "Extra Rect: " << actual_out.id_set << "(" << actual_out.rect
 395                 << ")" << std::endl;
 396     }
 397   }
 398
 399   return 0;
 400 }
 401
 402 #endif