src/2geom/sweep.cpp

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