Space partition tree

“Smart data structures and dumb code work a lot better than the other way around.” — Eric S. Raymond

7 min readMay 25, 2018

Disclaimer 1 : I’m french (for historical reasons and because of the food too). So, in order to make this reading more realistic, read this with a slight french accent.
Disclaimer 2 : Exemple shown here are in C++, but this kind of tree is language and platform independent. Those code could be greatly improved, but I want to keep it simple for non C++ expert.

I think it’s a relatively well known subject, but the first time I tried to implement a QuadTree, I struggled for a long time. So, in the unlikely event that someone needs anexplanation about space partition tree, maybe they will found in this article some help.

It’s about organizing some user data depending of their spatial position ; it will become easier to retrieve those object by position. This data structure is used heavily in graphics engine, collision engine, spatial database and many other domain for a long time. They may have different name depending on the dimension number (1D, 2D, …) or the partition strategy, but they are all the same kind.

Too long didn’t read

A space partition tree is a tree where each node recursively divide space. Objects added to the tree are in a node relatively to their position. The tree grows as object are added to the tree, and shrinks as their are removed. The main advantage of such a tree is when searching for objects by position, you can exclude branch entirely. Reducing the number of test to perform. Even if any tree modification (addition, deletion and move) can be costly, search are very efficient. It exists many variant of space partition tree depending of the number of dimension or division and object placement strategy.

Binary space partition tree

Binary Space Partition tree (BSP Tree) is a tree where each node recursively divides space in two. And a node can contain an object only if it is spatially in the node spaces. Reciprocally, an object can’t be in a node if it’s not placed in the right space.

If you are searching for all object being in an area, you can prove that a node is not in this area, excluding all of his children. In case of a such search, you can exclude a lot of the tree, limiting the number of objects to test.

Tree structure

The first node represents all the space available. Each node can contain two child : dividing itself in two equal part. A node represents a limited space : it has a minimum and a maximum. It contains an only object positioned in the node interval. It grows as you add an object, and shrinks as you remove them. In order to stay in synchronization with each object, it needs to be responsible for their position (right to read, and exclusive right to write).

Expanding and limiting the tree

The first node contains all the space, you just have to specify those extremum. By default a node has no child and obviously contains no object. Center is deduced from maximum and minimum value just to make futur computation easier. When a child is created, thus extremum are computed from the father ones and the side it will represent (the bool side).

When adding object, at some point, you will need to create children, recursively reducing space. But you have to limit this process. If not, the last node will be too small to contain any object and can even be too small to be coded (a interval smaller than 1 make no sens when using integer value). When the maximum depth is reached, you must add object somewhere (depending of your strategy). In our case, if too many object are added, we will overthrow the object limit and add them in the leaf node (the deeper one).

When removing object, you can delete a child as long as it’s empty. It keeps the tree from using too much memory when not needed. It’s not mandatory and should be avoid in case of very dynamic environment.

Adding, deleting and moving objects

Objects are added in the first node having room to hold it. First objects added will be in the root node, they can be anywhere in the available space. When this node is full, we create two empty children (if not done yet), each one representing half part of the parent node. After we checked in which node the object belongs to and passes it to the corresponding child. The process is repeated on each child until one can hold the object or maximum depth is reached. In such a case, the object will be added in the last node. Since the tree is responsible for the object position, it sets it after the process. Adding an object can be considered as a time consuming procedure, cost increasing with the tree size.

To remove an object from the tree, you have to find it. You will search it in each node recursively, using its position to take the right branch at each step. When it’s found, you just remove it and return. When an object is removed, you should remove empty branch to save memory, but at the cost of speed efficiency. Removing an object is a time consuming task too, yet less than the addition.

Since the tree is responsible of the object position, it has to move object itself, and updates it internal structure. Same as previously, you must first find the object, using it’s position. But at each branch, there are two cases : if the old and new position are in the same branch or not. If yes, you call the movObjectfunction recursively. If you find it by doing so, you are lucky, you have nothing more to do. If not, you have to delete the object from the old branch and add it to the other one, calling respective methods. Doing that, updates the tree internals states. After that, you just need to update the position of the object itself. This process is the most expensive one in time. In many cases, it result in doing a deletion and an addition sequentially, two costly tasks.

Retrieving objects

Here the whole point of this mess. Retrieving all object in an interval (or a delimited space). It is really simple, you test all object in all node being in the interval. The great part is, if a node is not in the interval, you can dismiss this branch in your search without any doubt. This action is fast. The more the tree grows, the smaller each node will be. Your benefit will grow with the tree.

Case of non punctual objects

For non-punctual objects, an object can be at the border of two node. In this case you are left with only two choice : putting it in the parent node, or in the both children. To put it in the parent node is not a very smart choice, all objects in the middle of the space will fill the root node, loosing all benefit. The other strategy is to put it in the both, but in this case, you will end up with the same object being in many node. You will need to adapt all previous recursion rules according to this new rule.

Benefits

When searching for anything at a specific position (or in an interval), you can exclude with certitude whole branch of the tree, reducing greatly the number of test to perform. Even if adding, removing or moving object can be costly, you will have substantial gain at every search.

You can fit to almost any particular case by tweaking the condition for an object to be in parent node or in the child. You can use as parameter the surface of the object (smaller it is, deeper it should be). An other strategy could work following the probability of an object to move, or their speed. The less it move, deeper it is.

QuadTree, OctTree — General case

ABSP tree is in one dimension only. When you deal with higher dimension, you will divide recursively the space in more part. In two dimension, you divide each node in four equal part (upper left, upper right and so on) : it’s a QuadTree. With three dimension, you will divide each node in eight part : OctTree. The general case is : with N dimensions, you will divide each node in 2 power to N children. In tweaking a little all previous algorithm, you will have a space partition tree in the number of dimension you need.

KDTree

A special case is when objects don’t move, a static tree. A more efficient way to implement this one is to balance the tree according to objects position. You will not divide space in equal spatial part, but you will try to balance the number of object in each branch.

By doing so you will minimize the number of test to perform in most of cases (and improving greatly your worse case). In this kind of tree, adding, removing or moving object are extremely costly operations, resulting in a modification of nearly all the tree at each time. In the other side, researchs can be very efficient in such a structure.

Use cases

Anytime you deal with a great number of object, and you need to interact a lot with (or according to) their position, a space partition tree should be useful. The only big constraint coming with this kind of tree is the space limitation : changing the size of the working space can be very costly and difficult. But in all other case, it is a very efficient and easy way to reduce ressource consumption.

It is used a lot in video gamse and graphics engine since Doom. It can be a collision detection system in itself (if you get all objects in a target position, you will have all object colliding with this target). It is used in spatial database and can work with other geometry and even with non numerical key. The very general concept is to recursively divide the liberty space.