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) const
70 if (!xdir && !ydir) return start;
72 QuadTreeIndex newNode;
73 // Try moving to the right if that's easy.
76 switch (nodes[start].child_type)
81 if (nodes[start].child_type == QTC_TOP_LEFT)
82 newNode = nodes[nodes[start].parent].top_right;
84 newNode = nodes[nodes[start].parent].bottom_right;
86 return GetNeighbour(newNode, xdir - 1, ydir);
89 case QTC_BOTTOM_RIGHT:
91 QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
92 if (right_parent == -1) return -1;
93 if (nodes[start].child_type == QTC_TOP_RIGHT)
94 newNode = nodes[right_parent].top_left;
96 newNode = nodes[right_parent].bottom_left;
97 return GetNeighbour(newNode, xdir - 1, ydir);
105 // Try moving to the left.
108 switch (nodes[start].child_type)
111 case QTC_BOTTOM_RIGHT:
113 if (nodes[start].child_type == QTC_TOP_RIGHT)
114 newNode = nodes[nodes[start].parent].top_left;
116 newNode = nodes[nodes[start].parent].bottom_left;
118 return GetNeighbour(newNode, xdir + 1, ydir);
121 case QTC_BOTTOM_LEFT:
123 QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
124 if (left_parent == -1) return -1;
125 if (nodes[start].child_type == QTC_TOP_LEFT)
126 newNode = nodes[left_parent].top_right;
128 newNode = nodes[left_parent].bottom_right;
129 return GetNeighbour(newNode, xdir + 1, ydir);
136 // Try moving to the bottom.
139 switch (nodes[start].child_type)
144 if (nodes[start].child_type == QTC_TOP_LEFT)
145 newNode = nodes[nodes[start].parent].bottom_left;
147 newNode = nodes[nodes[start].parent].bottom_right;
149 return GetNeighbour(newNode, xdir, ydir - 1);
151 case QTC_BOTTOM_LEFT:
152 case QTC_BOTTOM_RIGHT:
154 QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
155 if (bottom_parent == -1) return -1;
156 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
157 newNode = nodes[bottom_parent].top_left;
159 newNode = nodes[bottom_parent].top_right;
160 return GetNeighbour(newNode, xdir, ydir - 1);
167 // Try moving up, towards the sky.
170 switch (nodes[start].child_type)
172 case QTC_BOTTOM_LEFT:
173 case QTC_BOTTOM_RIGHT:
175 if (nodes[start].child_type == QTC_BOTTOM_LEFT)
176 newNode = nodes[nodes[start].parent].top_left;
178 newNode = nodes[nodes[start].parent].top_right;
180 return GetNeighbour(newNode, xdir, ydir + 1);
185 QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
186 if (top_parent == -1) return -1;
187 if (nodes[start].child_type == QTC_TOP_LEFT)
188 newNode = nodes[top_parent].bottom_left;
190 newNode = nodes[top_parent].bottom_right;
191 return GetNeighbour(newNode, xdir, ydir + 1);