Code

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