1 #include "sweep.h"
3 #include <algorithm>
5 namespace Geom {
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());
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());
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 }
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);
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 }
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 }
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;
95 std::vector<unsigned> all;
96 for(unsigned j = 0; j < b; j++)
97 all.push_back(j);
99 for(unsigned i = 0; i < a; i++)
100 ret.push_back(all);
102 return ret;
103 }
105 }
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 :