I'm implementing a quadtree. For those who don't know this data structure, I am including the following small description:
A Quadtree is a data structure and is in the Euclidean plane what an Octree is in a 3-dimensional space. A common use of quadtrees is spatial indexing.
To summarize how they work, a quadtree is a collection — let's say of rectangles here — with a maximum capacity and an initial bounding box. When trying to insert an element into a quadtree which has reached its maximal capacity, the quadtree is subdivided into 4 quadtrees (a geometric representation of which will have a four times smaller area than the tree before insertion); each element is redistributed in the subtrees according to its position, ie. the top left bound when working with rectangles.
So a quadtree is either a leaf and has less elements than its capacity, or a tree with 4 quadtrees as children (usually north-west, north-east, south-west, south-east).
My concern is that if you try to add duplicates, may it be the same element several times or several different elements with the same position, quadtrees have a fundamental problem with handling the edges.
For instance, if you work with a quadtree with a capacity of 1 and the unit rectangle as the bounding box:
And you try inserting twice a rectangle the upper-left bound of which is the origin: (or similarly if you try inserting it N+1 times in a quadtree with a capacity of N>1)
quadtree->insert(0.0, 0.0, 0.1, 0.1) quadtree->insert(0.0, 0.0, 0.1, 0.1)
The first insert will not be a problem:
But then the first insert will trigger a subdivision (because the capacity is 1):
Both rectangles are thus put in the same subtree.
Then again, the two elements will arrive in the same quadtree and trigger a subdivison…
And so on, and so forth, the subdivision method will run indefinitely because (0, 0) will always be in the same subtree out of the four created, meaning an infinite recursion problem occurs.
Is it possible to have a quadtree with duplicates? (If not, one may implement it as a
How can we solve this problem without breaking completely the architecture of a quadtree?