1 #ifndef QUADTREE_REMOVED
6 Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
13 if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
17 if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
24 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
27 if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
31 if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
42 bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
45 Rect dst = TransformFromQuadChild(std, child_type);
46 if (src.x + src.w < dst.x) return false;
47 if (src.y + src.h < dst.y) return false;
48 if (src.x > dst.x + dst.w) return false;
49 if (src.y > dst.y + dst.h) return false;
50 Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
54 bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
57 Rect dst = TransformFromQuadChild(std, child_type);
58 if (src.x < dst.x) return false;
59 if (src.y < dst.y) return false;
60 if (src.x + src.w > dst.x + dst.w) return false;
61 if (src.y + src.h > dst.y + dst.h) return false;
62 Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
68 QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
70 if (!xdir && !ydir) return start;
72 // Try moving to the right if that's easy.
75 switch (nodes[start].child_type)
79 QuadTreeIndex newNode;
80 if (nodes[start].child_type == QTC_TOP_LEFT)
81 newNode = node[nodes[start].parent].top_right;
83 newNode = node[nodes[start].parent].bottom_right;
85 return GetNeighbour(newNode, xdir - 1, ydir);
87 case QTC_BOTTOM_RIGHT:
88 QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
89 if (right_parent == -1) return -1;
90 QuadTreeIndex newNode;
91 if (nodes[start].child_type == QTC_TOP_RIGHT)
92 newNode = node[right_parent].top_left;
94 newNode = node[right_parent].bottom_left;
95 return GetNeighbour(newNode, xdir - 1, ydir);
100 // Try moving to the left.
103 switch (nodes[start].child_type)
106 case QTC_BOTTOM_RIGHT:
107 QuadTreeIndex newNode;
108 if (nodes[start].child_type == QTC_TOP_RIGHT)
109 newNode = node[nodes[start].parent].top_left;
111 newNode = node[nodes[start].parent].bottom_left;
113 return GetNeighbour(newNode, xdir + 1, ydir);
115 case QTC_BOTTOM_LEFT:
116 QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
117 if (left_parent == -1) return -1;
118 QuadTreeIndex newNode;
119 if (nodes[start].child_type == QTC_TOP_LEFT)
120 newNode = node[left_parent].top_right;
122 newNode = node[left_parent].bottom_right;
123 return GetNeighbour(newNode, xdir + 1, ydir);
128 // Try moving to the bottom.
131 switch (nodes[start].child_type)
135 QuadTreeIndex newNode;
136 if (nodes[start].child_type == QTC_TOP_LEFT)
137 newNode = node[nodes[start].parent].bottom_left;
139 newNode = node[nodes[start].parent].bottom_right;
141 return GetNeighbour(newNode, xdir, ydir - 1);
142 case QTC_BOTTOM_LEFT:
143 case QTC_BOTTOM_RIGHT:
144 QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
145 if (bottom_parent == -1) return -1;
146 QuadTreeIndex newNode;
147 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
148 newNode = node[bottom__parent].top_left;
150 newNode = node[bottom_parent].top_right;
151 return GetNeighbour(newNode, xdir, ydir - 1);
156 // Try moving up, towards the sky.
159 switch (nodes[start].child_type)
161 case QTC_BOTTOM_LEFT:
162 case QTC_BOTTOM_RIGHT:
163 QuadTreeIndex newNode;
164 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
165 newNode = node[nodes[start].parent].top_left;
167 newNode = node[nodes[start].parent].top_right;
169 return GetNeighbour(newNode, xdir, ydir + 1);
171 case QTC_BOTTOM_LEFT:
172 QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
173 if (top_parent == -1) return -1;
174 QuadTreeIndex newNode;
175 if (nodes[start].child_type == QTC_TOP_LEFT)
176 newNode = node[top_parent].bottom_left;
178 newNode = node[top_parent].bottom_right;
179 return GetNeighbour(newNode, xdir, ydir + 1);