kd tree plus proche voisin 2 dimensions

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!

Citation:

---

Envoyé par sophie2048

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...

---

Pour un point "P" quelconque, on cherche le 1er candidat "C" par le même algo que l'insertion.

S'il existe des meilleurs candidats ils sont forcément dans le cercle de centre "P" et passant par "C". Ils sont aussi nécessairement dans des "box" du kd-tree.

La première question est donc: quelles sont les box du kd-tree qui contiennent une partie du cercle ?

http://blog.blackpepper.co.uk/wp-con...ur-search1.png

Réponse: celles qui ont un coté qui intersecte le cercle.