Kd-tree vs octree to search for 3d radius

Question

I'm trying to figure out which structure would be better for doing a few searches for the radius of points, kd-tree or octet? This has already been mentioned in this question , but there was no answer. It seems to me that, since the axes have fixed sizes for the leaves, it is already possible to calculate the branches that I need to visit, and for a kd-tree you will have to iteratively visit the branches until the radius is covered.

Answer 1

For a three-dimensional and fixed query radius, octopuses are a good choice. If you need to work on disk, other data structures may be better, but kd-tree also does not shine here.

Why don't you try both and see what works best for your data?

Answer 2

In my project, I use Octree to search for a range, and it works efficiently and is easily implemented. Never compared it to KD-Tree. As far as I know, the worst time complexity in kd-trees for this operation is O (n ^ (2/3)) for three-dimensional data, while Octree can only guarantee O (n). Therefore, if you care about the worst difficulty of the time, choose KD Tree. (I don't care about the worst time complexity if I know that this will never happen in my dataset.)

Answer 3

I realized both personally and for that purpose I would definitely vote for an octet. It was much easier for me to get more effective results with an octet. I say simpler because I think that with such subtle differences this is more related to implementation more than to data structure. But I think that for most people it will be easier for you to optimize the octet.

One reason is that KD trees are inherently deeper than binary trees that split one dimension at a time. This deeper nature may be useful if you are looking for the exact matching element on the sheet, for example, to intersect the rays / triangles with a single, unambiguous path down the tree. This is useful when a deep tree, carefully divided, matches the idea of ​​search quality.

It is not very useful to have a deep, carefully divided tree if you are looking for the closest point in the maximum radius, where you end up spending most of the time just climbing up and down the tree, from leaf to parent to brother and grandparents to parent brother and etc. There it helps to be a little flatter if you can access everything with caching, and you can easily make octet caching the same as storing all 8 children, and at this point you can just do this:

struct OctreeNode { // Index of first child node. To get to the 4th node, // we just access nodes[first_child+3], eg int first_child; ... }; 

Anyway, I voted for an octet in this case, if these are two options. In addition, for this type of proximity search, you do not need to have the octet too deep. Even if we need to look for more points than optimal, with a smaller tree, it might be better than going up and down the tree. This helps if the points you keep in the sheet are contiguous. You can achieve this with a subsequent process after you finish building your tree.

Pay attention to both solutions that you should look at siblings. The closest point to point is not necessarily the one that is in the same node sheet. There are also some cases where only a three-dimensional grid can actually be optimal enough for this purpose, depending on the nature of your data, since with a three-dimensional grid you do not even need to switch from a child to a parent's brother. 3D meshes may seem explosive in memory usage, but they don't have to be if you reduce the mesh cell overhead by a 32-bit index. In this case, the 100x100x100 grid takes up less than 4 megabytes.