True!
Cavets:
- @groma knows better than me
- Per https://en.wikipedia.org/wiki/K-d_tree#High-dimensional_data how well a KDTree performs for a given dimensionality depends on how much stuff is in there. According to that wikipedia page you need many more data points than 2 to the power of your dimensions for it to do better than a brute force search.
I’m not sure what ‘many more’ might really mean though, but at least an order of magnitude I’d guess. So for 10 dimensions, at least ~10k entries? For 6 dimensions > 640 points. Etc. - I don’t know how well SC’s
KDTree
really scales up. I think development may have stopped before all the bits were done. Certainly, I started to make it wheeze trying even 3D radius searches at one point. - Beyond a certain point, Approximate Nearest Neighbours can be Good Enough
at potentially much lower cost, but that’s not yet available for any creative coding platform, AFAIK.