← Back to branch summary

~ubuntu-branches/debian/experimental/inkscape/experimental

« back to all changes in this revision

Viewing changes to src/2geom/sweep.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Viehmann
  • Date: 2008-09-09 23:29:02 UTC
  • mfrom: (1.1.7 upstream)
  • Revision ID: james.westby@ubuntu.com-20080909232902-c50iujhk1w79u8e7
Tags: 0.46-2.1
http://bugs.debian.org/487623
* Non-maintainer upload.
* Add upstream patch fixing a crash in the open dialog
  in the zh_CN.utf8 locale. Closes: #487623.
  Thanks to Luca Bruno for the patch.

Show diffs side-by-side

added added

removed removed

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