Incremental creation of KD-TREE

[karry3775]

Hi,
I wanted to know if there is a way to incrementally add points to the kd-tree, like say one at a time. What I basically want to achieve is run the kd-tree generation inside a loop so that the tree expands every time it receives a new element.
Thanks!

[tommasocarella]

Hi @karry3775 ! Did you find any way to implement this? I was thinking of using the KDTreeSingleIndexDynamicAdaptor which presents methods for addition and removal of points. Did you find a better way?

[karry3775]

Unfortunately, I am not using that feature for now, so stopped looking into it. You can close the issue and reopen later if need be.

…

On Sat, Mar 20, 2021 at 3:41 PM Yash Bansod ***@***.***> wrote: @karry3775 <https://github.com/karry3775>, @tommasocarella <https://github.com/tommasocarella>, did you find a good way of doing this? I want to do a similar thing for adding nodes to the NN in my tree incrementally. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#139 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AKLHQTYXH7V6BN7RDDXH5T3TET25ZANCNFSM4U3RAY6A> .

[dschwen]

KDTreeSingleIndexDynamicAdaptor seems to create a "forrest" of kd-trees. Every point set addition creates a new tree. When searching, each tree needs to be queried for a consolidated result. This will increase lookup times. Looks like depending on frequency of insertion vs. frequency of lookups, when you get to a certain number of sub-trees it might be beneficial to re-index all points as a new tree to improve lookup performance again.