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

nearest neighbour kd-tree

This topic is 3987 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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!