1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#include "sweep.h"
#include <algorithm>
namespace Geom {
std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> rs) {
std::vector<Event> events; events.reserve(rs.size()*2);
std::vector<std::vector<unsigned> > pairs(rs.size());
for(unsigned i = 0; i < rs.size(); i++) {
events.push_back(Event(rs[i].left(), i, false));
events.push_back(Event(rs[i].right(), i, true));
}
std::sort(events.begin(), events.end());
std::vector<unsigned> open;
for(unsigned i = 0; i < events.size(); i++) {
unsigned ix = events[i].ix;
if(events[i].closing) {
std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);
//if(iter != open.end())
open.erase(iter);
} else {
for(unsigned j = 0; j < open.size(); j++) {
unsigned jx = open[j];
if(rs[jx][Y].intersects(rs[ix][Y])) {
pairs[jx].push_back(ix);
}
}
open.push_back(ix);
}
}
return pairs;
}
std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> a, std::vector<Rect> b) {
std::vector<std::vector<unsigned> > pairs(a.size());
if(a.empty() || b.empty()) return pairs;
std::vector<Event> events[2];
events[0].reserve(a.size()*2);
events[1].reserve(b.size()*2);
for(unsigned n = 0; n < 2; n++) {
unsigned sz = n ? b.size() : a.size();
events[n].reserve(sz*2);
for(unsigned i = 0; i < sz; i++) {
events[n].push_back(Event(n ? b[i].left() : a[i].left(), i, false));
events[n].push_back(Event(n ? b[i].right() : a[i].right(), i, true));
}
std::sort(events[n].begin(), events[n].end());
}
std::vector<unsigned> open[2];
bool n = events[1].front() < events[0].front();
unsigned i[2] = {0};
while( i[n] < events[n].size()) {
unsigned ix = events[n][i[n]].ix;
bool closing = events[n][i[n]].closing;
//std::cout << n << "[" << ix << "] - " << (closing ? "closer" : "opener") << "\n";
if(closing) {
open[n].erase(std::find(open[n].begin(), open[n].end(), ix));
} else {
if(n) {
//n = 1
//opening a B, add to all open a
for(unsigned j = 0; j < open[0].size(); j++) {
unsigned jx = open[0][j];
if(a[jx][Y].intersects(b[ix][Y])) {
pairs[jx].push_back(ix);
}
}
} else {
//n = 0
//opening an A, add all open b
for(unsigned j = 0; j < open[1].size(); j++) {
unsigned jx = open[1][j];
if(b[jx][Y].intersects(a[ix][Y])) {
pairs[ix].push_back(jx);
}
}
}
open[n].push_back(ix);
}
i[n]++;
n = (events[!n][i[!n]] < events[n][i[n]]) ? !n : n;
}
return pairs;
}
//Fake cull, until the switch to the real sweep is made.
std::vector<std::vector<unsigned> > fake_cull(unsigned a, unsigned b) {
std::vector<std::vector<unsigned> > ret;
std::vector<unsigned> all;
for(unsigned j = 0; j < b; j++)
all.push_back(j);
for(unsigned i = 0; i < a; i++)
ret.push_back(all);
return ret;
}
}
|
