I'm currently implementing a collision detection system using quadtrees. I was able to implement the quadtree, but I had a question regarding a particular situation. Lets say my initial quadtree has a boundary of 200x200. So my 1st level of sub-quadtrees will have a boundary of:
NW: (0, 0) ~ (100,100)
SW: (0, 100) ~ (100, 200)
NE: (100, 0) ~ (200, 100)
SE: (100, 100) ~ (200, 200)
Lets say there is an square object at (98, 98), and its width and height are 5. I take the center position when inserting them into the sub-trees, so this object will be placed in the NW quadtree. However, since its width and height are 5, they are technically also on all other 3 quadtrees. Will I have to check if the object's boundary spans to the other side of the quadtree, and if yes, add multiple instance into the quadtree?
Yes -- either that or, upon insertion, split your square up into 4 separate ones in this case. Easier is just allow duplicates to be stored at the leaves, and make that cheap (pointer/index to the square, e.g.)
You can also make a loose-fitting tree where you just pick one of the children to insert this square, but expand its bounding box to fit. In those cases, you have overlapping partitions and have to recursively descend down the tree to search, so it has its pros and cons.
Another thing you can do is allow elements to be stored in the branches and not just the leaves. In that case, if an element wants to go into multiple children, just store it at the branch instead of descending further. For this, you have to check for elements at each branch during traversal and not just at the leaves.
I'd suggest just starting out with duplicates. The other methods can be a real hassle, and no need to bother with such hassle (until you measure a need for it).
These kinds of elements that have an area at the dead center of any branch can want to make your tree really deep and imbalanced, so you typically want a healthy stop gap to prevent that from recursing forever. It's typically not a big issue unless you have a boatload of elements like this.
Also, for 2D cases, you can sometimes get away with a fixed grid. It can actually work better sometimes to just have an NxM grid than a quad-tree since it's so simple to build (which makes it easier to update quickly for very dynamic content where you have, say, sprites moving around on the screen every frame), and doesn't have tricky worst-case scenarios since it doesn't have this notion of "depth", just cells containing elements.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments