Comment implémenter la recherche du plus proche voisin en utilisant KDTrees?

Question

Donc, je suis en train d'implémenter un KD-Tree pour faire une recherche de voisin le plus proche. J'ai la construction de la partie de l'arbre qui fonctionne, mais je ne pense pas que je comprends la partie de la recherche complètement.

A propos traversant l'arbre pour rechercher le voisin, l'article de Wikipedia dit le texte suivant:

Starting with the root node, the algorithm moves down the tree recursively, in the same 
way that it would if the search point were being inserted (i.e. it goes right or left 
depending on whether the point is greater or less than the current node in the split 
dimension). 

Que signifie « plus ou moins que le nœud actuel dans la dimension de la broche Qu'entendez-on compare les points de base? sur la distance de la requête ou est-ce que nous comparons les points par la dimension fendue

Aussi, quelqu'un pourrait expliquer la partie sur l'hyperespace et l'hyperplan? Je me sens comme je le comprends, mais puisque je ne suis pas sûr que je voudrais quelques explications supplémentaires

Merci!

Answer 1

Chaque noeud divise l'espace en 2 demi-espaces le long d'un axe. Vous regardez où le point en question est relatif à ce plan divisé pour décider quel côté de l'arbre à descendre. Par exemple si votre point est (4,7,12) et que vous avez un plan de division qui coupe l'axe y à 9, vous comparez le 7 au 9 et décidez de descendre le côté gauche (moins que) du kd arbre en premier. Après avoir trouvé le voisin le plus proche du côté gauche, vous vérifiez s'il est plus proche que 2 (la distance au plan de division: 9-7). Si elle est plus proche que le split-plane, vous n'avez pas du tout besoin de traverser l'autre demi-arbre. C'est pourquoi cela fonctionne si bien que la plupart du temps vous n'aurez qu'à traverser un sous-arbre.

Espérons que ça aide.