Jump to content
  • Advertisement
Sign in to follow this  
luca-deltodesco

nearest neighbour kd-tree

This topic is 3811 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Im working through kd-tree's. I've managed to get a working algorithm (although optimizations are needed) for generating a kd-tree for a set of points in 2D and 3D. And for traversing a kd-tree to find the leaf containing an outside point. But i'm a bit lost on an effecient algorithm for calculating the nearest neighbour in a kd-tree. The algorithm i had in my head, was to traverse the tree for the leaf containing the point. Find the nearest neighbour inside of this point. and then work up through the parent nodes back to the root testing any other nodes who's cell boundary is close enough for any cell or point inside of it to contain a closer point to the current one. However from wikipedia, it says that you start from the root node and work down, and im a bit confused on how that works, it also talks about intersecting prisms and other shit. Anyways help me with a work through of the best nearest neighbour algorithm for a kd-tree?

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!