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