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