Bonjour!
J essaie de comprendre l'algorithme du plus proche voisin à partir d un kd tree
(en 2 dimensions) mais je bloque.
Ce que j ai compris jusqu'ici c est qu'il faut descendre le long de l'arbre comme si on voulait insérer le point dont on cherche le plus proche voisin.
Ce dernier point est un candidat pour être le plus proche voisin.
Ensuite il faut remonter et voir si les points par lesquels on passe sont plus proche encore que le candidat.
Ce que je ne comprend pas ce sont c'est plan qui sont de toute façon trop loin et qu'on a pas besoin d'aller explorer.. Comment sait on si on doit explorer l'autre côté d'un point par lequel on passe ou pas..? Je le vois sur la représentation de l'arbre (avec les droite vertical et horizontal pour x et y) mais je ne comprend pas comment ça apparait dans l'algorithme...
Merci pour votre aide, bonne soirée!
Partager