![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
diff --git a/src/2geom/sweep.cpp b/src/2geom/sweep.cpp
index 4329bc55925ea8eaf055672807d13121bd94f169..7571efe094b671c8080bcd64927d102cb43564db 100644 (file)
--- a/src/2geom/sweep.cpp
+++ b/src/2geom/sweep.cpp
-#include "sweep.h"\r
-\r
-#include <algorithm>\r
-\r
-namespace Geom {\r
-\r
-std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> rs) {\r
- std::vector<Event> events; events.reserve(rs.size()*2);\r
- std::vector<std::vector<unsigned> > pairs(rs.size());\r
- \r
- for(unsigned i = 0; i < rs.size(); i++) {\r
- events.push_back(Event(rs[i].left(), i, false));\r
- events.push_back(Event(rs[i].right(), i, true));\r
- }\r
- std::sort(events.begin(), events.end());\r
-\r
- std::vector<unsigned> open;\r
- for(unsigned i = 0; i < events.size(); i++) {\r
- unsigned ix = events[i].ix;\r
- if(events[i].closing) {\r
- std::vector<unsigned>::iterator iter = std::find(open.begin(), open.end(), ix);\r
- //if(iter != open.end())\r
- open.erase(iter);\r
- } else {\r
- for(unsigned j = 0; j < open.size(); j++) {\r
- unsigned jx = open[j];\r
- if(rs[jx][Y].intersects(rs[ix][Y])) {\r
- pairs[jx].push_back(ix);\r
- }\r
- }\r
- open.push_back(ix);\r
- }\r
- }\r
- return pairs;\r
-}\r
-\r
-std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> a, std::vector<Rect> b) {\r
- std::vector<std::vector<unsigned> > pairs(a.size());\r
- if(a.empty() || b.empty()) return pairs;\r
- std::vector<Event> events[2];\r
- events[0].reserve(a.size()*2);\r
- events[1].reserve(b.size()*2);\r
- \r
- for(unsigned n = 0; n < 2; n++) {\r
- unsigned sz = n ? b.size() : a.size();\r
- events[n].reserve(sz*2);\r
- for(unsigned i = 0; i < sz; i++) {\r
- events[n].push_back(Event(n ? b[i].left() : a[i].left(), i, false));\r
- events[n].push_back(Event(n ? b[i].right() : a[i].right(), i, true));\r
- }\r
- std::sort(events[n].begin(), events[n].end());\r
- }\r
-\r
- std::vector<unsigned> open[2];\r
- bool n = events[1].front() < events[0].front();\r
- for(unsigned i[] = {0,0}; i[n] < events[n].size();) {\r
- unsigned ix = events[n][i[n]].ix;\r
- bool closing = events[n][i[n]].closing;\r
- //std::cout << n << "[" << ix << "] - " << (closing ? "closer" : "opener") << "\n";\r
- if(closing) {\r
- open[n].erase(std::find(open[n].begin(), open[n].end(), ix));\r
- } else {\r
- if(n) {\r
- //n = 1\r
- //opening a B, add to all open a\r
- for(unsigned j = 0; j < open[0].size(); j++) {\r
- unsigned jx = open[0][j];\r
- if(a[jx][Y].intersects(b[ix][Y])) {\r
- pairs[jx].push_back(ix);\r
- }\r
- }\r
- } else {\r
- //n = 0\r
- //opening an A, add all open b\r
- for(unsigned j = 0; j < open[1].size(); j++) {\r
- unsigned jx = open[1][j];\r
- if(b[jx][Y].intersects(a[ix][Y])) {\r
- pairs[ix].push_back(jx);\r
- }\r
- }\r
- }\r
- open[n].push_back(ix);\r
- }\r
- i[n]++;\r
- n = (events[!n][i[!n]] < events[n][i[n]]) ? !n : n;\r
- }\r
- return pairs;\r
-}\r
-\r
-//Fake cull, until the switch to the real sweep is made.\r
-std::vector<std::vector<unsigned> > fake_cull(unsigned a, unsigned b) {\r
- std::vector<std::vector<unsigned> > ret;\r
- \r
- std::vector<unsigned> all;\r
- for(unsigned j = 0; j < b; j++)\r
- all.push_back(j);\r
- \r
- for(unsigned i = 0; i < a; i++)\r
- ret.push_back(all);\r
- \r
- return ret;\r
-}\r
-\r
-}\r
+#include <2geom/sweep.h>
+
+#include <algorithm>
+
+namespace Geom {
+
+/**
+ * \brief Make a list of pairs of self intersections in a list of Rects.
+ *
+ * \param rs: vector of Rect.
+ * \param d: dimension to sweep along
+ *
+ * [(A = rs[i], B = rs[j]) for i,J in enumerate(pairs) for j in J]
+ * then A.left <= B.left
+ */
+
+std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> rs, Dim2 d) {
+ 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][d][0], i, false));
+ events.push_back(Event(rs[i][d][1], 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][1-d].intersects(rs[ix][1-d])) {
+ pairs[jx].push_back(ix);
+ }
+ }
+ open.push_back(ix);
+ }
+ }
+ return pairs;
+}
+
+/**
+ * \brief Make a list of pairs of red-blue intersections between two lists of Rects.
+ *
+ * \param a: vector of Rect.
+ * \param b: vector of Rect.
+ * \param d: dimension to scan along
+ *
+ * [(A = rs[i], B = rs[j]) for i,J in enumerate(pairs) for j in J]
+ * then A.left <= B.left, A in a, B in b
+ */
+std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> a, std::vector<Rect> b, Dim2 d) {
+ 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++) {
+ Rect r = n ? b[i] : a[i];
+ events[n].push_back(Event(r[d][0], i, false));
+ events[n].push_back(Event(r[d][1], i, true));
+ }
+ std::sort(events[n].begin(), events[n].end());
+ }
+
+ std::vector<unsigned> open[2];
+ bool n = events[1].front() < events[0].front();
+ {// As elegant as putting the initialiser in the for was, it upsets some legacy compilers (MS VS C++)
+ unsigned i[] = {0,0};
+ for(; 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][1-d].intersects(b[ix][1-d])) {
+ 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][1-d].intersects(a[ix][1-d])) {
+ pairs[ix].push_back(jx);
+ }
+ }
+ }
+ open[n].push_back(ix);
+ }
+ i[n]++;
+ if(i[n]>=events[n].size()) {break;}
+ 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;
+}
+
+}
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :