3 ms·
How easy is it to extend k-d trees to deal with objects with finite size (vs. points)? Are there any libraries that do this? I might have to do something simila
by electricslpnsld 9y ago
How easy is it to extend k-d trees to deal with objects with finite size (vs. points)? Are there any libraries that do this? I might have to do something similar to this in the future, but I need nearest neighbors for 'spheres' in higher dimensions.
- geophile 9y agoRelated to another thread on this discussion: Z-order combined with sorted array/tree/etc. generalizes to non-point objects quite easily. I think the Z-order NN algorithm will "just work" with non-point data.
- snaily 9y agoIf by "just work" you mean testing each constituent vertex, it'll fail. Consider the case when the needle is at the midpoint of a line between two points far away.
- geophile 9y agoNo, that's not what I mean. A point is represented by a z-value at the resolution of space. A non-point is approximated by multiple z-values, at varying resolutions. You can trade the accuracy of the approximation against the number of z-values. I explained the NN algorithm in another comment on this thread. It shouldn't matter if some of the adjacent z-values are actually from the approximation of the same object.
- rwbt 9y agoAABB Trees (Axis Aligned Bounding Box) might be an option. Most realtime collision detection systems utilize them.
- yoklov 9y agoOr more generally bounding volume hierarchies, of which AABB trees are a subset. They’re great. Good perf, while being one of the simpler ways of accelerating spatial queries (compared to other types of trees, at least)
- pubby 9y agoSee r-trees, interval trees, and ball trees.
- gmueckl 9y agok-d trees can be used with things like lines and triangles. This was pretty common in computer graphics for a while. There is also a generalization called BSP tree that allows for arbitrary split planes. The catch with both is that you need to be careful with primitives that intersect split planes. You either need to introduce either additional bookkeeping to avoid testing the same primitive multiple times, or you need to split the primitives at each plane. Both are not really desirable properties. Also, primitives that lie exactly on a split plane will lead to unstable results as the tests involving the split plane and the primitive are usually bound to to give slightly different results. A bounding volume hierarchy is generally easier to implement and more reliable. And people have optimised the heck out of algorithms to construct them.