Discussion :

[developpeurP00]

Bonjour.

J'ai besoin de l'aide pour avoir un pseudo algorithme (ou code scilab, ou octave )qui trouve les k plus proches voisins d'un point M dans un ensemble E de points

E= [point1 ; point2 ; ............ ; pointn] inclus dans un espace D

exemple point= [15 4 8 -9 ]

pour pouvoir implémenter une recherche rapide , on m'a demandé de choisir E avec un partitionnement l'espace D par kd-tree

J'ai besoin svp alors de cet algorithme de partitionnement et l'algorithme de recherche aussi

merci

[Matthieu Brucher]

Pour le découpage, c'est simple, tu découpe en cube selon chaque direction.

En gros, tant que tu veux découper, tu découpes tes plus grandes dimensions en 2, et tu mets dans l'arbre les points associés.

Pour la recherche, à partir d'un point, tu commences à chercher dans la feuille courante.

Tu mets dans une liste triée les noeuds qui entourent ta feuille classés par leur distance minimale. Si tu as suffisamment de voisins et que la distance maximale de ces voisins est inférieure à la distance minimale, tu as fini. Sinon, tu prends le noeud le plus proche. Si c'est une feuille, mets à jour tes voisins. Sinon, tu mes les feuilles filles dans la liste des noeuds voisins.
Tu itères.

J'ai écrit en C++ ce code il y a quelques années, c'est très facile à s'imaginer. Il suffit de bien réfléchir à ce qu'il faut faire.

[developpeurP00]

merci pour votre aide. pouvez vous me donner un lien internet où c'est expliqué cette discrétisation . je n'ai jamais eu l'occasion de rencontrer cette méthode. Merci

[Matthieu Brucher]

Je n'ai jamais eu de lien non plu, donc je ne pourrai pas en donner.

[developpeurP00]

Merci

pour ce qui leur intéresse .j'ai trouvé ce lien

http://www.irisa.fr/prive/kadi/DIIC/...ose_KdTree.pdf

[Matthieu Brucher]

Sauf que ça n'a strictement rien à voir avec ce que tu cherches ! Il te faut des cases de taille la plus carrée possible. Un kdtree pour lancer de rayon, c'est exactement l'opposé.

[Invité]

pour pouvoir implémenter une recherche rapide , on m'a demandé de choisir E avec un partitionnement l'espace D par kd-tree

J'ai besoin svp alors de cet algorithme de partitionnement et l'algorithme de recherche aussi

Il y a une implémentation correcte des kd Tree dans Numerical Recipes 3eme édition, et une autre dans le Cormen, Leiserson, Rivest. Les deux sont généralement présents dans toutes les bonnes bibliothèques.

Sinon, il y a un peu de code là
http://en.wikipedia.org/wiki/Kd-tree
et là
http://www.codeproject.com/KB/architecture/KDTree.aspx

Francois