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 QuadTreeIndex newNode;
74 // Try moving to the right if that's easy.
77 switch (nodes[start].child_type)
82 if (nodes[start].child_type == QTC_TOP_LEFT)
84 newNode = nodes[nodes[start].parent].top_right;
85 if (addTo && newNode == -1)
87 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
92 newNode = nodes[nodes[start].parent].bottom_right;
93 if (addTo && newNode == -1)
95 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
98 return GetNeighbour(newNode, xdir - 1, ydir, addTo);
101 case QTC_BOTTOM_RIGHT:
103 QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
104 if (right_parent == -1) return -1;
105 if (nodes[start].child_type == QTC_TOP_RIGHT)
107 newNode = nodes[right_parent].top_left;
108 if (addTo && newNode == -1)
110 newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
115 newNode = nodes[right_parent].bottom_left;
116 if (addTo && newNode == -1)
118 newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
121 return GetNeighbour(newNode, xdir - 1, ydir, addTo);
129 // Try moving to the left.
132 switch (nodes[start].child_type)
135 case QTC_BOTTOM_RIGHT:
137 if (nodes[start].child_type == QTC_TOP_RIGHT)
139 newNode = nodes[nodes[start].parent].top_left;
140 if (addTo && newNode == -1)
142 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
147 newNode = nodes[nodes[start].parent].bottom_left;
148 if (addTo && newNode == -1)
150 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
154 return GetNeighbour(newNode, xdir + 1, ydir, addTo);
157 case QTC_BOTTOM_LEFT:
159 QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
160 if (left_parent == -1) return -1;
161 if (nodes[start].child_type == QTC_TOP_LEFT)
163 newNode = nodes[left_parent].top_right;
164 if (addTo && newNode == -1)
166 newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
171 newNode = nodes[left_parent].bottom_right;
172 if (addTo && newNode == -1)
174 newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
177 return GetNeighbour(newNode, xdir + 1, ydir, addTo);
184 // Try moving to the bottom.
187 switch (nodes[start].child_type)
192 if (nodes[start].child_type == QTC_TOP_LEFT)
194 newNode = nodes[nodes[start].parent].bottom_left;
195 if (addTo && newNode == -1)
197 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
202 newNode = nodes[nodes[start].parent].bottom_right;
203 if (addTo && newNode == -1)
205 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
208 return GetNeighbour(newNode, xdir, ydir - 1, addTo);
210 case QTC_BOTTOM_LEFT:
211 case QTC_BOTTOM_RIGHT:
213 QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
214 if (bottom_parent == -1) return -1;
215 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
217 newNode = nodes[bottom_parent].top_left;
218 if (addTo && newNode == -1)
220 newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
225 newNode = nodes[bottom_parent].top_right;
226 if (addTo && newNode == -1)
228 newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
231 return GetNeighbour(newNode, xdir, ydir - 1, addTo);
238 // Try moving up, towards the sky.
241 switch (nodes[start].child_type)
243 case QTC_BOTTOM_LEFT:
244 case QTC_BOTTOM_RIGHT:
246 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
248 newNode = nodes[nodes[start].parent].top_left;
249 if (addTo && newNode == -1)
251 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
256 newNode = nodes[nodes[start].parent].top_right;
257 if (addTo && newNode == -1)
259 newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
262 return GetNeighbour(newNode, xdir, ydir + 1, addTo);
267 QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
268 if (top_parent == -1) return -1;
269 if (nodes[start].child_type == QTC_TOP_LEFT)
271 newNode = nodes[top_parent].bottom_left;
272 if (addTo && newNode == -1)
274 newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
279 newNode = nodes[top_parent].bottom_right;
280 if (addTo && newNode == -1)
282 newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
285 return GetNeighbour(newNode, xdir, ydir + 1, addTo);