1 #include <2geom/sweep.h>
3 #include <algorithm>
5 namespace Geom {
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 */
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());
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());
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 }
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);
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 }
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 }
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;
114 std::vector<unsigned> all;
115 for(unsigned j = 0; j < b; j++)
116 all.push_back(j);
118 for(unsigned i = 0; i < a; i++)
119 ret.push_back(all);
121 return ret;
122 }
124 }
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 :