From e730f9001a4b673c03fed92a26ebee39941fa675 Mon Sep 17 00:00:00 2001 From: "Johan B. C. Engelen" Date: Sun, 23 Dec 2007 19:34:02 +0000 Subject: update to latest 2geom (fixed 2 bugs :)) (bzr r4284) --- src/2geom/sweep.cpp | 208 ++++++++++++++++++++++++++-------------------------- 1 file changed, 104 insertions(+), 104 deletions(-) (limited to 'src/2geom/sweep.cpp') diff --git a/src/2geom/sweep.cpp b/src/2geom/sweep.cpp index 08674ab2f..96104ea90 100644 --- a/src/2geom/sweep.cpp +++ b/src/2geom/sweep.cpp @@ -1,104 +1,104 @@ -#include "sweep.h" - -#include - -namespace Geom { - -std::vector > sweep_bounds(std::vector rs) { - std::vector events; events.reserve(rs.size()*2); - std::vector > 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 open; - for(unsigned i = 0; i < events.size(); i++) { - unsigned ix = events[i].ix; - if(events[i].closing) { - std::vector::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 > sweep_bounds(std::vector a, std::vector b) { - std::vector > pairs(a.size()); - if(a.empty() || b.empty()) return pairs; - std::vector 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 open[2]; - bool n = events[1].front() < events[0].front(); - for(unsigned i[] = {0,0}; 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 > fake_cull(unsigned a, unsigned b) { - std::vector > ret; - - std::vector 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; -} - -} +#include "sweep.h" + +#include + +namespace Geom { + +std::vector > sweep_bounds(std::vector rs) { + std::vector events; events.reserve(rs.size()*2); + std::vector > 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 open; + for(unsigned i = 0; i < events.size(); i++) { + unsigned ix = events[i].ix; + if(events[i].closing) { + std::vector::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 > sweep_bounds(std::vector a, std::vector b) { + std::vector > pairs(a.size()); + if(a.empty() || b.empty()) return pairs; + std::vector 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 open[2]; + bool n = events[1].front() < events[0].front(); + for(unsigned i[] = {0,0}; 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 > fake_cull(unsigned a, unsigned b) { + std::vector > ret; + + std::vector 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; +} + +} -- cgit v1.2.3