Quadtree with duplicates

Question

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:

[(0,0),(0,1),(1,1),(1,0)]

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 Set)

How can we solve this problem without breaking completely the architecture of a quadtree?

Answer 1

You're implementing a data structure, so you have to make implementation decisions.

Unless the quadtree has something specific to say about uniqueness - and I'm not aware that it does - this is an implementation decision. It's orthogonal to the definition of a quadtree and you can choose to handle it however you want. The quadtree tells you how to insert and update keys, but not whether they have to be unique, or what you can attach to each node.

Making implementation decisions is not reinventing the wheel, at least no more than writing your own implementation in the first place.

For comparison, the C++ standard library offers a unique set, a non-unique multiset, a unique map (essentially a set of key-value pairs ordered & compared only by the key) and a non-unique multimap. They're all typically implemented using the same red-black tree and none are breaking the architecture, simply because the definition of the red-black tree has nothing to say about the uniqueness of keys or the types stored in leaf nodes.

Finally, if you think there's research on this, find it, and then we can discuss it. Maybe there is some quadtree invariant I've overlooked, or some additional constraint that allows better performance.

Answer 2

I am assuming that you are indexing elements that are all of about the same size, otherwise life gets complex, or slow, or both……

A Quadtree node does not need to have a fixed capacity. The capacity is used to

• Allow each tree node to be fixed size in memory or on disk – not required if the tree node contains a variable sized set of elements and you are using a space allocation system that copes. (E.g. java/c# objects in memory.)
• Decide when to split a node.
  • You could just redefine the rule, so that a node is split if it contains more than “n” district elements, where district is defined in according to the location of the elements.
  • Or use a “composite element”, so if there are multiply elements at the same location, you introduce a new element that contains a list of these multiply elements.

Answer 3

When you're dealing with spatial indexing problems, I actually recommend starting off with a spatial hash or my personal favorite: the plain old grid.

... and understand its weaknesses first before moving to tree structures that allow sparse representations.

One of the obvious weaknesses is that you could be wasting memory on a lot of empty cells (though a decently-implemented grid shouldn't require more than 32-bits per cell unless you actually have billions of nodes to insert). Another is that if you have moderate-sized elements which are larger than the size of a cell and often span, say, dozens of cells, you can waste a lot of memory inserting those medium-sized elements to far more cells than ideal. Likewise when you do spatial queries, you might have to check more cells, sometimes far more, than ideal.

But the only thing to finesse with a grid to make it as optimal as it can be against a certain input is cell size, which doesn't leave you with too much to think about and fiddle with, and that's why it's my go-to data structure for spatial indexing problems until I find reasons not to use it. It's dirt simple to implement and doesn't require you to fiddle with anything more than a single runtime input.

You can get a lot out of a plain old grid and I've actually beaten a lot of quad-tree and kd tree implementations used in commercial software by replacing them with a plain old grid (though they weren't necessarily the best implemented ones, but the authors spent a whole lot more time than the 20 mins I spent to whip up a grid). Here's a quick little thing I whipped up to answer a question elsewhere using a grid for collision detection (not even really optimized, just a few hours of work, and I had to spend most of the time learning how the pathfinding works to answer the question and it was also my first time implementing collision-detection of this sort):

Another weakness of grids (but they are general weaknesses for many spatial indexing structures) is that if you insert a lot of coincident or overlapping elements, like many points with the same position, they are going to be inserted into the exact same cell(s) and degrade performance when traversing that cell. Similarly if you insert a lot of massive elements that are far, far bigger than the cell size, they'll want to be inserted into a boatload of cells and use lots and lots of memory and degrade the time required for spatial queries across the board.

However, these two immediate problems above with coincident and massive elements are actually problematic for all spatial indexing structures. The plain old grid actually handles these pathological cases a little bit better than many others since it at least doesn't want to recursively subdivide cells over and over.

When you start with the grid and work your way towards something like a quad-tree or KD-tree, then the main problem you're wanting to solve is the problem with elements being inserted to too many cells, having too many cells, and/or having to check too many cells with this type of dense representation.

But if you think of a quad-tree as an optimization over a grid for specific use cases, then it does help to still think of the idea of a "minimum cell size", to limit the depth of the recursive subdivision of the quad-tree nodes. When you do that, the worst-case scenario of the quad-tree will still degrade into the dense grid at the leaves, only less efficient than the grid since it'll require logarithmic time to work your way from root to grid cell instead of constant-time. Yet thinking of that minimum cell size will avoid the infinite loop/recursion scenario. For massive elements there are also some alternative variants like loose quad-trees which don't necessarily split evenly and could have AABBs for child nodes that overlap. BVHs are also interesting as spatial indexing structures which don't evenly subdivide their nodes. For coincident elements against tree structures, the main thing is to just impose a limit to the subdivision (or as others suggested, just reject them, or find a way to treat them as though they aren't contributing to the unique number of elements in a leaf when determining when the leaf should subdivide). A Kd tree might also be useful if you anticipate inputs with a lot of coincident elements, since you only need to consider one dimension when determining whether a node should median split.

Answer 4

I think there is a misapprehension here.

As I understand it, every quadtree node contains a value indexed by a point. In other words, it contains the triple (x,y,value).

It also contains 4 pointers to child nodes, which may be null. There is an algorithmic relationship between the keys and the child links.

Your inserts should look like this.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

The first insert creates a (parent) node and inserts a value into it.

The second insert creates a child node, links to it, and inserts a value into it (which may happen to be the same as the first value).

Which child node is instantiated depends on the algorithm. If the algorithm is in the form [x) and the coordinate space lies in the range [0,1) then each child will span the range [0,0.5) and the point will be placed in the NW child.

I see no infinite recursion.

Answer 5

The common resolution I have come across (in visualisation problems, not in games) is to ditch one of the points, either always replacing or never replacing.

I suppose the main point in favour is that it is easy to do.