Redistribute current points to children when subdividing

[mvdmee]

Although the Wiki implementation does not do it but the tree gets better when you move all the points in the current item to its children when subdividing (and redirect all further insert to its children).
In the end points will only reside in the leaves of the tree.

When using the current implementation there are many points being queried that are not even close to the searched range. For instance the points in the root element are always queried no matter where you search. When redistributing to the child nodes you can save about 50% off the points you need to query.

[crhallberg]

Hey! I just started looking into this and there's a problem. If you have a QuadTree with a capacity of 4 and you try to add 5 identically positioned points, it will loop forever. All these points will always end up in the same subdivision, overflowing it, splitting, overwhelming the new subdivision, etc.

Is there a solution to this?

[crhallberg]

One solution I found in a very thorough write-up on QuadTrees is setting a maximum depth to the tree. This seems like an effective solution to this particular edge case.

Source: https://stackoverflow.com/a/48330314

[crhallberg]

I have conflicting feelings about this issue. You are correct that moving all of the data to the leaves does create a more performant and technically accurate quadtree. However, as a potential learning tool where this repository is not just code but also a way to understand quadtrees, I'm concerned this change could erode the simplicity of the current system.

I'd be interested to see what @shiffman thinks. I could start a pull request in the meantime.

@crhallberg I created an example of quadtree that drill down the points to the corresponding quadrant.
it really seems that the query is faster when the points are crowded , but however when I try to detect between 5000 objects, my implementation is 10 fps less than this repo example.

https://codesandbox.io/s/github/sayeko/quadtree-collision-detection

[crhallberg]

I really love this demo! I might try to re-implement it with this QuadTree.