I'm implementing an immutable Quadtree in Scala and I can't understand what happens/when to split a node. These are my main references: Article 1, Article 2 and a third one I can't find now.
I understand these 3 key points of a quadtree:
- A node contains an object in its subtree if the object at least intersects the area covered by the node.
- A Quadtree has a maximum depth D and the actual depth can be different for different branches
- A leaf node can contain a maximum of K objects before it splits and becomes an intermediate node.
Note: objects are not points but they are 2D shapes.
My current implementation allows for intermediate nodes to hold objects but I want to simplify it and allow objects only on the leaves, but this raises a doubt.
Let's assume K=2. What happens if a have node that already contains 2 objects that covers most of its area and I add a 3rd big one one? The node splits into 4 children (point 3 above). All the 3 objects can intersect the children, so they are all moved to the each child (point 1 above). But now each child has to split and move the object to their children as they can hold only 2 objects and so on recursively.
This cycle continues indefinitely (which is bad) or until depth=D (point 2 above).
It doesn't look like having a full-depth tree just for 3 objects is a good thing. I end up with loads of pointers on many leaves to the same 3 objects and I have to scan the whole depth to look for collisions. And also insertion looks very costly.
What's wrong with my understanding?
