Using k-d trees to efficiently calculate nearest neighbors in 3D vector space

Re:Using k-d trees to efficiently calculate nearest neighbor... by electricslpnsld on Saturday February 10, 2018 @05:37PM (#16350043)

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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by rwbt on Saturday February 10, 2018 @05:58PM (#16350121)

AABB Trees (Axis Aligned Bounding Box) might be an option. Most realtime collision detection systems utilize them.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by yoklov on Sunday February 11, 2018 @03:02AM (#16351717)

Or 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)

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by gmueckl on Sunday February 11, 2018 @03:13AM (#16351743)

k-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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Saturday February 10, 2018 @06:10PM (#16350177)

Related 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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by snaily on Sunday February 11, 2018 @08:06PM (#16355807)

If 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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by geophile on Sunday February 11, 2018 @11:02PM (#16356441)

No, 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.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by pubby on Saturday February 10, 2018 @09:43PM (#16350891)

See r-trees, interval trees, and ball trees.

[ Parent | on HN ]