src/2geom/sweep.cpp

   1 #include "sweep.h"\r
   2 \r
   3 #include <algorithm>\r
   4 \r
   5 namespace Geom {\r
   6 \r
   7 std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> rs) {\r
   8     std::vector<Event> events; events.reserve(rs.size()*2);\r
   9     std::vector<std::vector<unsigned> > pairs(rs.size());\r
  10 \r
  11     for(unsigned i = 0; i < rs.size(); i++) {\r
  12         events.push_back(Event(rs[i].left(), i, false));\r
  13         events.push_back(Event(rs[i].right(), i, true));\r
  14     }\r
  15     std::sort(events.begin(), events.end());\r
  16 \r
  17     std::vector<unsigned> open;\r
  18     for(unsigned i = 0; i < events.size(); i++) {\r
  19         unsigned ix = events[i].ix;\r
  20         if(events[i].closing) {\r
  21             std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);\r
  22             //if(iter != open.end())\r
  23             open.erase(iter);\r
  24         } else {\r
  25             for(unsigned j = 0; j < open.size(); j++) {\r
  26                 unsigned jx = open[j];\r
  27                 if(rs[jx][Y].intersects(rs[ix][Y])) {\r
  28                     pairs[jx].push_back(ix);\r
  29                 }\r
  30             }\r
  31             open.push_back(ix);\r
  32         }\r
  33     }\r
  34     return pairs;\r
  35 }\r
  36 \r
  37 std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> a, std::vector<Rect> b) {\r
  38     std::vector<std::vector<unsigned> > pairs(a.size());\r
  39     if(a.empty() || b.empty()) return pairs;\r
  40     std::vector<Event> events[2];\r
  41     events[0].reserve(a.size()*2);\r
  42     events[1].reserve(b.size()*2);\r
  43 \r
  44     for(unsigned n = 0; n < 2; n++) {\r
  45         unsigned sz = n ? b.size() : a.size();\r
  46         events[n].reserve(sz*2);\r
  47         for(unsigned i = 0; i < sz; i++) {\r
  48             events[n].push_back(Event(n ? b[i].left() : a[i].left(), i, false));\r
  49             events[n].push_back(Event(n ? b[i].right() : a[i].right(), i, true));\r
  50         }\r
  51         std::sort(events[n].begin(), events[n].end());\r
  52     }\r
  53 \r
  54     std::vector<unsigned> open[2];\r
  55     bool n = events[1].front() < events[0].front();\r
  56     for(unsigned i[] = {0,0}; i[n] < events[n].size();) {\r
  57         unsigned ix = events[n][i[n]].ix;\r
  58         bool closing = events[n][i[n]].closing;\r
  59         //std::cout << n << "[" << ix << "] - " << (closing ? "closer" : "opener") << "\n";\r
  60         if(closing) {\r
  61             open[n].erase(std::find(open[n].begin(), open[n].end(), ix));\r
  62         } else {\r
  63             if(n) {\r
  64                 //n = 1\r
  65                 //opening a B, add to all open a\r
  66                 for(unsigned j = 0; j < open[0].size(); j++) {\r
  67                     unsigned jx = open[0][j];\r
  68                     if(a[jx][Y].intersects(b[ix][Y])) {\r
  69                         pairs[jx].push_back(ix);\r
  70                     }\r
  71                 }\r
  72             } else {\r
  73                 //n = 0\r
  74                 //opening an A, add all open b\r
  75                 for(unsigned j = 0; j < open[1].size(); j++) {\r
  76                     unsigned jx = open[1][j];\r
  77                     if(b[jx][Y].intersects(a[ix][Y])) {\r
  78                         pairs[ix].push_back(jx);\r
  79                     }\r
  80                 }\r
  81             }\r
  82             open[n].push_back(ix);\r
  83         }\r
  84         i[n]++;\r
  85         if(i[n]>=events[n].size()) {break;}\r
  86         n = (events[!n][i[!n]] < events[n][i[n]]) ? !n : n;\r
  87     }\r
  88     return pairs;\r
  89 }\r
  90 \r
  91 //Fake cull, until the switch to the real sweep is made.\r
  92 std::vector<std::vector<unsigned> > fake_cull(unsigned a, unsigned b) {\r
  93     std::vector<std::vector<unsigned> > ret;\r
  94 \r
  95     std::vector<unsigned> all;\r
  96     for(unsigned j = 0; j < b; j++)\r
  97         all.push_back(j);\r
  98 \r
  99     for(unsigned i = 0; i < a; i++)\r
 100         ret.push_back(all);\r
 101 \r
 102     return ret;\r
 103 }\r
 104 \r
 105 }\r