QuadTree suggestion

Jan 23, 2007 at 5:34 PM

I noticed a possible problem in the QuadTree implementation.

The IntersectTreeRecursive adds all nodes to the search list if the node is a leaf. The problem is that it appears that the intersection test, done in the parent call, is not done correctly.

For instance, if Search is called on a Tree with a single node, all nodes in the tree will be added to the search list, even if the BoundingBox provided in the Search call does not intersect with the nodes BoundingBox. Or more likely, if a node contains two child leaf nodes, all of those children will be added to the Search list, even if the search boundingbox only intersects with one of them. This is because the intersection test is done with the parent node and not the children.

I hope that makes sense. I would suggest changing the IntersectTreeRecursive method as follows:

if (!node.Box.Intersects(box)) { return; }

if (node.IsLeaf) //Leaf has been reached
{
for (int i = 0; i < node._objList.Count;i++ )
list.Add(node._objListi.ID);
}
else
{
IntersectTreeRecursive(box, node.Child0, ref list);
IntersectTreeRecursive(box, node.Child1, ref list);
}