|
1
by Jasper van de Gronde
Initial commit |
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 |
* \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 |
*/
|
|
16 |
||
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()); |
|
20 |
||
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()); |
|
26 |
||
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 |
}
|
|
46 |
||
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); |
|
63 |
||
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 |
}
|
|
74 |
||
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 |
}
|
|
113 |
||
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; |
|
117 |
||
118 |
std::vector<unsigned> all; |
|
119 |
for(unsigned j = 0; j < b; j++) |
|
120 |
all.push_back(j); |
|
121 |
||
122 |
for(unsigned i = 0; i < a; i++) |
|
123 |
ret.push_back(all); |
|
124 |
||
125 |
return ret; |
|
126 |
}
|
|
127 |
||
128 |
}
|
|
129 |
||
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 :
|