J'ai un ensemble fixe de points de R^3 appelé P.
Ensuite a partir d'un point donné Xi je veux chercher son plus proche "voisin" dans P.
Pour l'instant je parcours tout P en calculant les normes. Et c'est horriblement long.
C'est sûr :)
J'ai vu dans des papiers sur le net que la solution classique a ce probleme etait les kd-tree. (d'ailleurs je vois pas trop encore comment faire pour trouver ce point le plus proche avec un kd-tree. quand je vais parcourir l'arbre, je vais choisir de partir a gauche ou a droite de mon plan de separation suivant les valeurs de Xi, mais rien ne me dit que la distance forcement meilleure !)
Donc si tu as des docs la dessus n'h'site pas.
Sinon comme le faisait remarquer qqn il y a pas mal d'implémentations libres que tu peux réutiliser ou au moins lire le code pour comprendre comment ça marche. Entre autres, il y a un module kd-tree dans Biopython http://www.biopython.org/ .
Sinon il n'y a pas que les kd-trees. Une autre technique qui peut marcher c'est de simplement découper ton volume en "cases" (bins en anglais) de taille fixes de façon à ce que tu n'ais qu'un petit nombre de points par case. Pour trouver le plus proche voisin d'un point, tu n'as plus qu'à tester les autres points dans sa case et éventuellement ceux des cases à côté. Enfin ça dépend de la distribution de tes points. Ça marche bien pour des atomes dans une molécule par exemple.
[^] # Re: En vrac
Posté par Vivi . En réponse au journal Écoles, classes prépas etc etc.... Évalué à 2.
Ensuite a partir d'un point donné Xi je veux chercher son plus proche "voisin" dans P.
Pour l'instant je parcours tout P en calculant les normes. Et c'est horriblement long.
C'est sûr :)
J'ai vu dans des papiers sur le net que la solution classique a ce probleme etait les kd-tree. (d'ailleurs je vois pas trop encore comment faire pour trouver ce point le plus proche avec un kd-tree. quand je vais parcourir l'arbre, je vais choisir de partir a gauche ou a droite de mon plan de separation suivant les valeurs de Xi, mais rien ne me dit que la distance forcement meilleure !)
Donc si tu as des docs la dessus n'h'site pas.
En gros il faut positionner ton point cible dans le kd-tree et ensuite tu dois remonter un peu dans l'arbre et regarder les points dans le noeuds proches. Y'a une explication là par exemple :
http://www.ri.cmu.edu/pub_files/pub1/moore_andrew_1991_1/moo(...)
Sinon comme le faisait remarquer qqn il y a pas mal d'implémentations libres que tu peux réutiliser ou au moins lire le code pour comprendre comment ça marche. Entre autres, il y a un module kd-tree dans Biopython http://www.biopython.org/ .
Sinon il n'y a pas que les kd-trees. Une autre technique qui peut marcher c'est de simplement découper ton volume en "cases" (bins en anglais) de taille fixes de façon à ce que tu n'ais qu'un petit nombre de points par case. Pour trouver le plus proche voisin d'un point, tu n'as plus qu'à tester les autres points dans sa case et éventuellement ceux des cases à côté. Enfin ça dépend de la distribution de tes points. Ça marche bien pour des atomes dans une molécule par exemple.