return of overlap_values about aabbtree HOT 6 CLOSED

By the way, I also have an extra question about the balancing method of the AABB tree. Recently, I am working on my project by using your implementation for the AABB tree. It is quite well right now in terms of accuracy and runtime, but after several experiments, I found the depth of the AABB tree sometimes could be extremely long, which indicates that the AABB tree degenerates into almost a chain in some sense. I think it will lose the advantage of the AABB tree when it comes into a chain. So, currently, I am hoping to get rid of that bad situation, but I am not sure which one causes it, input data, or the balancing method for the AABB tree? I saw there are a few ways to balance an AABB tree, but I am not sure which one is used here for it?

Besides, currently, I am using the following code to build the AABB tree.

for i in range(100)
            AABB_tree.add(leaf[i], value = i)

I think it may cause unbalancing of the AABB tree, so Is there any advanced way to build the AABB tree? For example, can we build it "once for all" instead of "adding it one by one"?

Thanks.

from aabbtree.

Hi @DRKWang I've created a branch with the option to return duplicate AABBs and their values from the tree.

For balance, have you tried both method='DFS' and method='BFS'?

I wrote the package initially for myself, used in another package where the bounds of box "i" depended on the bounds of boxes 0 to "i-1". I needed an incremental insertion method, but there's also top-down and bottom-up methods. The AABBTree.add method is incremental and attempts to add nodes to an existing tree, in a balanced way, by minimizing a heuristic. This is the best it can do when nodes are added incrementally, but the top-down and bottom-up methods are better when all the boxes are already defined.

I didn't need top-down or bottom-up methods when I initially wrote the package, but they're certainly useful. Would you be willing to look into these methods and submit a PR to add that functionality? I can help out, but I won't have time to code it myself in the next 6 months.

from aabbtree.

The option to return non-unique AABBs and their values has been added in v2.8.0.

from aabbtree.

Hi @DRKWang I've created a branch with the option to return duplicate AABBs and their values from the tree.

For balance, have you tried both method='DFS' and method='BFS'?

I wrote the package initially for myself, used in another package where the bounds of box "i" depended on the bounds of boxes 0 to "i-1". I needed an incremental insertion method, but there's also top-down and bottom-up methods. The AABBTree.add method is incremental and attempts to add nodes to an existing tree, in a balanced way, by minimizing a heuristic. This is the best it can do when nodes are added incrementally, but the top-down and bottom-up methods are better when all the boxes are already defined.

I didn't need top-down or bottom-up methods when I initially wrote the package, but they're certainly useful. Would you be willing to look into these methods and submit a PR to add that functionality? I can help out, but I won't have time to code it myself in the next 6 months.

Thanks for your help in adding the optional return of duplicate AABBs for me! It will be honorable for me to submit a PR and add that functionality. Perhaps, there be several ways to construct an AABB tree, so it would take a little time to program, but I would like to continuously update it.

from aabbtree.

Hi @DRKWang have you worked on this over the last year? If not, I'll close the issue.

from aabbtree.

Hi @kip-hart, I am really sorry that I do not have time to work on this, please close this issue.

from aabbtree.