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 |