News for hackers. Stuff that matters.

A comment on Using k-d trees to efficiently calculate nearest neighbors in 3D vector space. Parent comment

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 ]