Discussion :

[koni33]

Bonjour à tous.

J'ai cherché sur le forum et le site, j'ai pas trouvé d'info à ce sujet.

Je suis actuellement entrain d'implémenter un kd-tree, et je cherche à mettre en place un système de recherche du point le plus proche (par rapport à un point de référence n'appartenant pas au kd-tree).
Le seul site me donnant un algorithme pour cela est wikipedia.

Si j'ai bien compris, la première étape de l'algo consiste à trouver le noeud du graphe dans lequel serait le point de référence. Il faut ensuite vérifier que le noeud correspond au point le plus proche, ce qui n'est pas forcement le cas.
Et c'est là que je ne suis plus.
A partir de quel noeud dois-je commencer à tester les intersection hyperplan-hypersphere ?


Si quelqu'un à déjà bossé la dessus et pourrait me renseigner, ou si quelqu'un à un lien vers une version plus précise de l'algo, je suis preneur.

En vous remerciant,
Koni33

[pseudocode]

une petite recherche google m'a donné cette présentation PowerPoint avec un joli exemple, pas à pas : http://www.cse.ttu.edu.tw/~jmchen/co...s/NNkdtree.ppt

[koni33]

Je n'aime pas quand ça se fini comme cela... J'ai pourtant fouiné sur le net un petit moment. Bref.

Effectivement la présentation à l'air plutôt clair, je vais potasser tout ça.

Merci en tout cas,

Koni



Edit :
J'ai entre temps trouvé une autre version de l'algo, que j'ai commencé à implémenter. Elle fonctionne avec une pile LIFO. L'algo est expliqué ici : http://dimacs.rutgers.edu/Workshops/...dyk-slides.ppt
J'ai du mal à voir pourquoi les deux algo fonctionneraient tous les deux, je ne vois pas de similarités.