src/2geom/sweep.cpp

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