Discussion :

[arnoldo165]

Bonjour,

J'ai un problème assez simple à résoudre. Mais je ne trouve pas un méthode simple et propre.

J'ai un nuage de points dont je connais les coordonnées dans un espace à N dimensions. Ce que je souhaite c'est pour un point donné, trouver le point de l'ensemble qui soit le plus proche.

Mon ensemble de points n'évolue pas et je l'utilise ensuite pour approximer un très grand nombre de points. Je peux donc le structurer au départ même si ce travail de structuration est gourmand en terme de calcul. il ne sera fait qu'une fois.

Je penche vers une sorte de dichotomie dans l'espace me permettant de trouver le point le plus proche avec une complexité de l'ordre de logNe Np étant le nbre de point dans mon ensemble de départ.


Merci bcp pour tous vos tuyau

Arnaud Megret

[PRomu@ld]

Tu peux toujours utiliser un KD-tree, ça marche en ND et pour trouver les plus proches voisins, ça fonctionne pas trop mal.

[souviron34]

ou un Quick Sort sur la distance (au carré, comme ça pas de calcul de racine)

[ToTo13]

Bonjour,

pour avoir le point le plus proche, il te suffit de parcourir tes points et de calculer la distance avec la métrique de ton choix. La plus répandue étant la distance Euclidienne.
Sinon, si tu souhaites structurer tes points, tu peux tenter un petit Voronoï. Comme ça ton nouveau point appartiendra à une cellule et le point le plus proche sera parmi les points constituant la cellule.

[_Michel]

Si tu utilises pas trop de points et que tu dois déterminer souvent quel est le point le plus proche d'un autre :
A chaque fois que tu introduis un point dans ton "sac", tu détermines son point le plus proche par test sur chacun des points. Tu associes le point trouvé au nouveau point. Si ce nouveau point est le point le plus proche du point trouvé, alors tu associes le nouveau point au point trouvé. Comme chaque point "pointe" sur son point le plus proche.
Par contre c'est gourmand en espace mémoire si tu ne peux pas numéroter les points et si les coordonnées sont compliquées.

[arnoldo165]

Merci pour vos pistes.
J'ai implémenté la méthode avec un KD-Tree.
Dans sa phase préparatoire, cet algo divise la zone d'espace contenant les points en un arbre de zones imbriquées (hyper-pavés).
Les feuilles consistent en un petit hyper-pavé contenant un seul point.

La recherche consiste à trouver le pavé contenant le point recherché en partant de la zone racine. On suppose que le point le plus proche est le point du pavé.
puis, on s'assure qu'il ne peut pas y avoir un point candidat meilleur dans une zone adjacente en remontant jusqu'à la racine.

La complexité est en log(N) mais est très dépendante de la dimension de l'espace de recherche.

[tchize_]

Si tu veux une complexité de recherche relativement indépendante de la dimension, oriente toi vers un PAT tree, l'avantage est que c'est un arbre qui contient très peu de creux, quelle que soit la dimensiont (la séparation et la recherche se font en dimension 1, ce qui est rapide)