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