A quadtree is a tree data structure in which each internal node has exactly four children. …most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
So hopefully you have a better idea of what a quadtree is and how it will help us. If not then firstly sorry! And secondly, there are some great tutorials that go through it in a bit more detail. I personally love the interactive explanation that you can find here.
So what are we passing into the constructor:
- maxObjects: how many objects a node can contain before it splits into child nodes.
- maxLevels: starting from the base node (0) how many times can it (and its children) split.
- level: this is the current level of the tree. This is set to 0 in the default constructor as it is the base node.
- bounds: the area of the quadtree. This controls the position and size of the tree.
- parent: if this is a child node then parent node is included here, otherwise this will be a nulptr.
Let’s break the function down into its separate steps:
- It first needs to check if it has any children nodes. We assume if the first child node is present then all four nodes are because when we split the node we create the four children together.
- If this node has child nodes then we call a function (that we have not yet written) whose job is to return the index of the node that the object should belong to.
- If the function returns an index to a child node and not to this node then we call the child nodes insert function and return.
- At this point, we know that this node has no child nodes so we insert the object into this nodes collection.
- As we’ve added a new object we need to check if we have exceeded the maximum number of objects allowed in a node.
- If we exceed the object count limit we need initialise child nodes.
- And lastly, once we’ve split into child nodes we need to iterate over every object in this node and calculate if it should be in a child node instead.