Version imprimable
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
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.
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
Je n'ai jamais eu de lien non plu, donc je ne pourrai pas en donner.
Merci
pour ce qui leur intéresse .j'ai trouvé ce lien
http://www.irisa.fr/prive/kadi/DIIC/...ose_KdTree.pdf
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é.
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.Citation:
Envoyé par utilisateur38
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