1 #ifndef QUADTREE_REMOVED
7 Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
14 if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
18 if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
25 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
28 if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
32 if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
43 bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
46 Rect dst = TransformFromQuadChild(std, child_type);
47 if (src.x + src.w < dst.x) return false;
48 if (src.y + src.h < dst.y) return false;
49 if (src.x > dst.x + dst.w) return false;
50 if (src.y > dst.y + dst.h) return false;
51 //Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
55 bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
58 Rect dst = TransformFromQuadChild(std, child_type);
59 if (src.x < dst.x) return false;
60 if (src.y < dst.y) return false;
61 if (src.x + src.w > dst.x + dst.w) return false;
62 if (src.y + src.h > dst.y + dst.h) return false;
63 //Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
69 QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *addTo) const
71 if (!xdir && !ydir) return start;
73 if (addTo && (nodes[start].parent == -1) && nodes[start].child_type != QTC_UNKNOWN)
75 Debug("Adding parent of node %d...", start);
76 addTo->GenQuadParent(start, nodes[start].child_type);
79 QuadTreeIndex newNode;
80 // Try moving to the right if that's easy.
83 switch (nodes[start].child_type)
88 if (nodes[start].child_type == QTC_TOP_LEFT)
90 newNode = nodes[nodes[start].parent].top_right;
91 if (addTo && newNode == -1)
93 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
98 newNode = nodes[nodes[start].parent].bottom_right;
99 if (addTo && newNode == -1)
101 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
104 return GetNeighbour(newNode, xdir - 1, ydir, addTo);
107 case QTC_BOTTOM_RIGHT:
109 QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
110 if (right_parent == -1) return -1;
111 if (nodes[start].child_type == QTC_TOP_RIGHT)
113 newNode = nodes[right_parent].top_left;
114 if (addTo && newNode == -1)
116 newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
121 newNode = nodes[right_parent].bottom_left;
122 if (addTo && newNode == -1)
124 newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
127 return GetNeighbour(newNode, xdir - 1, ydir, addTo);
135 // Try moving to the left.
138 switch (nodes[start].child_type)
141 case QTC_BOTTOM_RIGHT:
143 if (nodes[start].child_type == QTC_TOP_RIGHT)
145 newNode = nodes[nodes[start].parent].top_left;
146 if (addTo && newNode == -1)
148 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
153 newNode = nodes[nodes[start].parent].bottom_left;
154 if (addTo && newNode == -1)
156 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
160 return GetNeighbour(newNode, xdir + 1, ydir, addTo);
163 case QTC_BOTTOM_LEFT:
165 QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
166 if (left_parent == -1) return -1;
167 if (nodes[start].child_type == QTC_TOP_LEFT)
169 newNode = nodes[left_parent].top_right;
170 if (addTo && newNode == -1)
172 newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
177 newNode = nodes[left_parent].bottom_right;
178 if (addTo && newNode == -1)
180 newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
183 return GetNeighbour(newNode, xdir + 1, ydir, addTo);
190 // Try moving to the bottom.
193 switch (nodes[start].child_type)
198 if (nodes[start].child_type == QTC_TOP_LEFT)
200 newNode = nodes[nodes[start].parent].bottom_left;
201 if (addTo && newNode == -1)
203 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
208 newNode = nodes[nodes[start].parent].bottom_right;
209 if (addTo && newNode == -1)
211 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
214 return GetNeighbour(newNode, xdir, ydir - 1, addTo);
216 case QTC_BOTTOM_LEFT:
217 case QTC_BOTTOM_RIGHT:
219 QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
220 if (bottom_parent == -1) return -1;
221 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
223 newNode = nodes[bottom_parent].top_left;
224 if (addTo && newNode == -1)
226 newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
231 newNode = nodes[bottom_parent].top_right;
232 if (addTo && newNode == -1)
234 newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
237 return GetNeighbour(newNode, xdir, ydir - 1, addTo);
244 // Try moving up, towards the sky.
247 switch (nodes[start].child_type)
249 case QTC_BOTTOM_LEFT:
250 case QTC_BOTTOM_RIGHT:
252 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
254 newNode = nodes[nodes[start].parent].top_left;
255 if (addTo && newNode == -1)
257 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
262 newNode = nodes[nodes[start].parent].top_right;
263 if (addTo && newNode == -1)
265 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
268 return GetNeighbour(newNode, xdir, ydir + 1, addTo);
273 QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
274 if (top_parent == -1) return -1;
275 if (nodes[start].child_type == QTC_TOP_LEFT)
277 newNode = nodes[top_parent].bottom_left;
278 if (addTo && newNode == -1)
280 newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
285 newNode = nodes[top_parent].bottom_right;
286 if (addTo && newNode == -1)
288 newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
291 return GetNeighbour(newNode, xdir, ydir + 1, addTo);