diff --git a/src/2geom/sweep.cpp b/src/2geom/sweep.cpp
index 1b881399036103801c60a7cfb02e44d757db34f4..7571efe094b671c8080bcd64927d102cb43564db 100644 (file)
--- a/src/2geom/sweep.cpp
+++ b/src/2geom/sweep.cpp
namespace Geom {
-std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> rs) {
+/**
+ * \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].left(), i, false));
- events.push_back(Event(rs[i].right(), i, true));
+ 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());
} else {
for(unsigned j = 0; j < open.size(); j++) {
unsigned jx = open[j];
- if(rs[jx][Y].intersects(rs[ix][Y])) {
+ if(rs[jx][1-d].intersects(rs[ix][1-d])) {
pairs[jx].push_back(ix);
}
}
return pairs;
}
-std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> a, std::vector<Rect> b) {
+/**
+ * \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];
@@ -45,15 +65,18 @@ std::vector<std::vector<unsigned> > sweep_bounds(std::vector<Rect> a, std::vecto
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));
+ 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();
- for(unsigned i[] = {0,0}; i[n] < events[n].size();) {
+ {// 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";
//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])) {
+ if(a[jx][1-d].intersects(b[ix][1-d])) {
pairs[jx].push_back(ix);
}
}
//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])) {
+ if(b[jx][1-d].intersects(a[ix][1-d])) {
pairs[ix].push_back(jx);
}
}
i[n]++;
if(i[n]>=events[n].size()) {break;}
n = (events[!n][i[!n]] < events[n][i[n]]) ? !n : n;
- }
+ }}
return pairs;
}