J'ai un point dans un plan 2D par exemple (x0, y0) et un ensemble de n points (x1, y1) ... (xn, yn) et je veux trouver le point le plus proche de (x0, y0 ) de manière meilleure que d'essayer tous les points. Toute solution?
Je devrais également dire que mes points sont triés de cette manière:
6 Réponses :
Pour une recherche de voisin la plus proche efficace, vous devez utiliser un schéma de partitionnement spatial, par exemple un k d-arbre .
Voronoi Diagram est conçu spécifiquement pour trouver le point le plus proche très rapidement. Bien que ce soit une douleur à mettre en œuvre, vous pouvez trouver une bibliothèque / mise en œuvre existante.
Il existe également une option pour diviser à plusieurs reprises le plan dans les carrés, construisant ainsi une sorte d'arbre où chaque nœud non feuille a 4 enfants (carré en haut à droite, carré inférieur droit, etc.). Ensuite, de quatre carrés, vous trouvez celui que votre point est votre point et continuez avec cela récursivement. Souvent, ces rendements pointaient suffisamment près, vous pouvez donc éliminer le besoin de vérifier d'autres carrés.
Mais il est facile de créer un «contre-exemple» pour cette stratégie qui entraînera une période linéaire.
Mais il n'y a pas grand chose que vous puissiez faire avec votre réseau de tri pour accélérer le processus. Vous aurez besoin d'une structure de données spéciale.
La deuxième structure s'appelle quadtree , grâce à
Bien que cela puisse sembler excessivement, vous dépensez O (N log n) Opérations construisant votre diagramme Voronoi, mais ensuite, chaque voisin le plus proche peut être recherché dans O (log n). Contrastez cela avec O (N) pour l'itération naïve. De plus, je recommande d'utiliser CGAL pour calculer le diagramme de Voronoi (par Delaunay Triangulation). CGAL est compliqué, mais l'algorithme Delaunay est très sensible aux erreurs de rondelle et vous ne devez pas la mettre en œuvre vous-même: vous avez besoin (entre autres) des numéros de point variant de précision adaptatifs.
Seul problème est de mettre en œuvre la structure de données :-). De plus, CGAL est une bibliothèque assez coûteuse à moins que vous soyez open-optimalant votre propre code.
@Daniel: Je ne savais pas que cgal était double licencié. La structure de données est en fait assez naturelle. Le problème réel réside dans le test instable de "étant dans un cercle circonscrit d'un triangle": si les points triangulaires sont presque alignés, le calcul est très inexact et donne la mauvaise triangulation.
@Alexandre oui je suis très bien conscient de ce problème :-). J'ai passé des mois à travailler sur un algorithme de triangulation essayant de le réparer. Bien sûr, je n'ai pas réussi et le mauvais code est toujours utilisé par des clients malheureux ...
@Daniel: J'ai bien peur de devoir utiliser des calculs de points flottants adaptatifs. Il y a beaucoup de façons de faire cela, je peux avoir des papiers à portée de main si vous êtes intéressé.
Si vous créez l'ensemble de n pointes, alors au lieu de simplement les pousser dans un ensemble, vous pouvez le récupérer et la cartographier en fonction de leur distance linéaire du point à l'examen. Donc, des points de même distance linéaire seront dans le même seau. Ensuite, la récupération du ou des points basée sur la distance sera une opération de temps constante.
Si vous n'utilisez aucune sorte de structure de données d'arbres pour limiter la plage de valeurs que vous devez interroger, vous devrez vérifier chaque point de votre gamme de «voisins» potentiels. Un moyen de limiter les comparaisons serait de vérifier la distance carrée de votre point donné pour la valeur la plus petite:
std :: Min_Element () fournit la réponse avec moins de complexité (max (n-1,0) comparaisons) que std :: Trier () (O (n · log (N)))). Exemption de la manipulation des erreurs, cela donne le point le plus proche: std :: min_element (...) -> pt .
@Martinmoene Oui, STD :: Min_Element est une bonne alternative à trier les distances carrées pour l'élément minimum.
X0 et Y0 sont-ils le premier élément de cette liste de points triés?
non. Il est complètement hors de la liste: D
Est le point arbitraire? Ça change? C'est-à-dire que vous voudrez plus tard trouver le point le plus proche de certains autre point?
Je veux peut-être interroger pour de nombreux points différents