Subversion Repositories Scribus

Rev

Rev 17163 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
12065 fschmid 1
#include "quadtree.h"
2
 
3
Quad* QuadTree::search(double x0, double y0, double x1, double y1) {
4
    Quad *q = root;
5
 
6
    double bxx0 = bx1, bxx1 = bx1;
7
    double byy0 = by1, byy1 = by1;
8
    while(q) {
9
        double cx = (bxx0 + bxx1)/2;
10
        double cy = (byy0 + byy1)/2;
11
        unsigned i = 0;
12
        if(x0 >= cx) {
13
            i += 1;
14
            bxx0 = cx; // zoom in a quad
15
        } else if(x1 <= cx) {
16
            bxx1 = cx;
17
        } else
18
            break;
19
        if(y0 >= cy) {
20
            i += 2;
21
            byy0 = cy;
22
        } else if(y1 <= cy) {
23
            byy1 = cy;
24
        } else
25
            break;
26
 
27
        assert(i < 4);
28
        Quad *qq = q->children[i];
29
        if(qq == 0) break; // last non-null
30
        q = qq;
31
    }
32
    return q;
33
}
34
 
35
void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) {
36
    // loop until a quad would break the box.
37
    if(root == 0) {
38
        root = new Quad;
39
 
40
        bx0 = 0;
41
        bx1 = 1;
42
        by0 = 0;
43
        by1 = 1;
44
    }
45
    Quad *q = root;
46
 
47
    double bxx0 = bx0, bxx1 = bx1;
48
    double byy0 = by0, byy1 = by1;
49
    while((bxx0 > x0) ||
50
          (bxx1 < x1) ||
51
          (byy0 > y0) ||
52
          (byy1 < y1)) { // too small initial size - double
53
        unsigned i = 0;
54
        if(bxx0 > x0) {
55
            bxx0 = 2*bxx0 - bxx1;
56
            i += 1;
57
        } else {
58
            bxx1 = 2*bxx1 - bxx0;
59
        }
60
        if(byy0 > y0) {
61
            byy0 = 2*byy0 - byy1;
62
            i += 2;
63
        } else {
64
            byy1 = 2*byy1 - byy0;
65
        }
66
        q = new Quad;
67
        q->children[i] = root;
68
        root = q;
69
        bx0 = bxx0;
70
        bx1 = bxx1;
71
        by0 = byy0;
72
        by1 = byy1;
73
    }
74
 
75
    while(q) {
76
        double cx = (bxx0 + bxx1)/2;
77
        double cy = (byy0 + byy1)/2;
78
        unsigned i = 0;
79
        assert(x0 >= bxx0);
80
        assert(x1 <= bxx1);
81
        assert(y0 >= byy0);
82
        assert(y1 <= byy1);
83
        if(x0 >= cx) {
84
            i += 1;
85
            bxx0 = cx; // zoom in a quad
86
        } else if(x1 <= cx) {
87
            bxx1 = cx;
88
        } else
89
            break;
90
        if(y0 >= cy) {
91
            i += 2;
92
            byy0 = cy;
93
        } else if(y1 <= cy) {
94
            byy1 = cy;
95
        } else
96
            break;
97
 
98
        assert(i < 4);
99
        Quad *qq = q->children[i];
100
        if(qq == 0) {
101
            qq = new Quad;
102
            q->children[i] = qq;
103
        }
104
        q = qq;
105
    }
106
    q->data.push_back(shape);
107
}
22497 jghali 108
 
12065 fschmid 109
void QuadTree::erase(Quad *q, int shape) {
22497 jghali 110
    Quad::iterator i = q->data.begin();
111
    while(i != q->data.end()) {
12065 fschmid 112
        if(*i == shape) {
22497 jghali 113
            i = q->data.erase(i);
114
            continue;
12065 fschmid 115
        }
22497 jghali 116
        i++;
12065 fschmid 117
    }
118
    return;
119
}
120
 
121
/*
122
  Local Variables:
123
  mode:c++
124
  c-file-style:"stroustrup"
125
  c-file-offsets:((innamespace . 0)(substatement-open . 0))
126
  indent-tabs-mode:nil
127
  c-brace-offset:0
128
  fill-column:99
129
  End:
130
  vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
131
*/
132