Discussion :

[norwy]

Bonjour,

Comment trouver le point le plus proche à partir d'une liste de points de façon optimale ?

Je pourrais bêtement boucler sur tous les point et définir le plus proche mais devant un grand nombre de points sur lesquels appliquer cette opération ce serait beaucoup trop lourd...

Ma fonction aurait ce prototype :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
Point nearestPointFrom(Point localisation, Vector pointList);

où localisation est le point à partir duquel on veut trouver le point le plus proche contenu dans la liste (vector) pointList.

[Jedai]

Je pourrais bêtement boucler sur tous les point et définir le plus proche mais devant un grand nombre de points sur lesquels appliquer cette opération ce serait beaucoup trop lourd...

Et tu voudrais faire comment pour déterminer quel est le point le plus proche de ta localisation sans tous les regarder.......
La seule "optimisation" qu'on puisse faire c'est de restreindre l'ensemble de recherche en partitionnant plus ou moins astucieusement l'espace et en admettant quelques heuristiques (il faut être prêt à accepter de ne pas être toujours parfaitement optimal). Evidemment ceci n'est valable que si on fait un nombre très important de recherche du point le plus proche.

--
Jedaï

[FrancisSourd]

Une autre optim est de stocker les points dans une structure de données autre qu'une liste (quadtrees par exemple). Fabriquer une telle structure n'est, comme le dit Jedaï:

... valable que si on fait un nombre très important de recherche du point le plus proche.

Voir aussi ce topic:
http://www.developpez.net/forums/vie....php?p=2192614

[Selenite]

Difficile de faire plus rapide que l'algorithme naïf. Calculer le carré de la distance d'un point à un autre n'est vraiment pas lourd. Tu peux essayer de commencer par comparer la distance horizontale à la plus petite distance déjà trouver. Ceci peut être intéressant, il faut tester la méthode pour savoir si c'est la cas ou non.

Si le point de comparaison est toujours le même, alors là tu peut faire des optimisations intéressantes. Tu peux par exemple stocker tes points dans un conteneur ordonné.

[random]

le problème va varier selon la fonction de croissance du nombre de points
déja on peut munir l'espace d'une frontière ou rectangle enserrant tous les points

quadriller l'espace en petits carrés
le point le plus proche se situe dans le carré d'origine ou dans un carré
contigu 4
pour les carrés frontaliers on a 3 cotés à examiner
si le nombre de points augmente on peut procéder ainsi
j'ai un nombre de points connus 1000 000
je délimite mon espace total
je crée par exemple 10000 carrés (dont 400 frontières) je classe mes points
je peux faire toutes mes comparaisons
les nouveaux points calculés prendront place dans une liste spéciale
égale à la taille de 5 carrés
quand je veux rechercher le voisin de x
j'ai la taille de mon espace et le nombre de carrés
je peux calculer mon adresse
je fais ma recherche dans mes 5 carrés si pas frontière plus ma liste
spéciale
quand ma liste atteint 105000 points je redispose l'ensemble
le nombre de comparaisons nécessaires varie avec racine de x dans cet
exemple si les points suivent une loi aléatoire
par contre si les points suivent une loi de distribution différente
il va falloir considérer des zones denses et des zones désertiques
là il faudra jouer sur un effet de zoom
avec des zones de quadrillage plus ou moins fin