Meilleur algorithme de performance critique pour la résolution du plus proche voisin

Question

Nous avons une liste de paires x, y. Chaque paire représente un point sur un espace 2D. Je veux trouver le point le plus proche de cette liste, à un point spécifique xq, yq. Quel est le meilleur algorithme de performance critique pour ce problème? Lisp de points ne va pas changer; ce qui signifie que je n'ai pas besoin d'effectuer une insertion et une suppression. Je veux juste trouver le voisin le plus proche d'un point cible xq, yq dans cet ensemble.

Édition 1: Merci à tous! Comme Stephan202 a deviné correctement, je veux le faire à plusieurs reprises; comme une fonction. Une liste n'est pas nécessairement triée (en fait je ne comprends pas comment elle peut être triée? Comme une table avec une clé primaire de 2 colonnes a et y? Si cela aide alors je vais le trier).

Je construirai la structure de données basée sur la liste une fois, puis j'utiliserai cette structure de données générée dans la fonction (si ce processus lui-même est pertinent).

Merci Jacob; Il semble que la structure de données de KD-Tree soit un bon candidat pour être la réponse (et je pense que c'est le cas, je le mettrai à jour quand j'obtiendra des résultats pertinents).

Édition 2: J'ai trouvé que, ce problème est nommé "plus proche voisin"!

Édition 3: Le premier titre était "À la recherche d'un algorithme (pour l'interrogation spatiale et l'indexation spatiale) (le plus proche voisin)"; J'ai choisi un nouveau titre: "Meilleur algorithme de performance critique pour résoudre le plus proche voisin". Puisque je ne veux pas effectuer d'opération d'insertion et de suppression sur mes données initiales et que je veux juste la plus proche d'elles vers un nouveau point (qui ne sera pas inséré), j'ai choisi de travailler (actuellement) sur KD-Trees. Merci à tous!

Answer 1

Comme Stephan202 a noté, si vous prévoyez de trouver la correspondance la plus proche pour plus d'un point, vous devez utiliser un arbre.

Je recommanderais un arbre KD, dont la mise en œuvre peut être facilement trouvée dans plusieurs paquets comme OpenCV 2.0. Ou vous pouvez en implémenter un vous-même!

EDIT: J'avais posé une question sur les implémentations de kd-tree here - pourrait être utile.

EDIT: KD-arbres ont été largement utilisés avec succès pour les recherches NN :) - En outre, si vous êtes prêt à accepter correspondances approximatives, vous pouvez utiliser Fast Library for Approximate Nearest Neigbor (FLANN). La mise en œuvre FLANN est présent dans OpenCV 2.0.

Si vous ne souhaitez pas de réponses approximatives, vous pouvez modifier les paramètres FLANN pour rechercher l'intégralité de l'arborescence.

Answer 2

Effectuez une itération sur tous les autres points en utilisant la formule de distance pour trouver la distance minimale de Q (xq, yq).

Cependant, vous n'avez pas donné suffisamment d'informations pour une réponse critique. Par exemple, si Q est un point TRÈS commun, vous voudrez peut-être calculer la distance à Q et la mémoriser avec chaque point.

Deuxième exemple, si vous avez un grand nombre de points, vous pouvez organiser des points en sections et commencer par des points que dans la même section et des sections adjacentes à la section contenant Q.

Answer 3

Si le point de requête (xq, yq) varie et que la liste ne le fait pas, vous devez calculer Voronoi diagram de la liste des points.Cela vous donnera un ensemble de polygones ou "cellules" (dont certaines sont infinies); chaque polygone correspond à un point de la liste d'origine, appelé "site" de cette cellule. Tout point situé entièrement à l'intérieur d'un polygone est plus proche du site de ce polygone que des autres sites de la liste d'origine. Tout point sur une limite entre deux polygones est également distant de chaque site. Une fois que vous êtes arrivé si loin, vous avez besoin d'un moyen facile de savoir dans quel polygone vous êtes. Ceci est connu sous le nom point location problem.

Un livre vraiment, vraiment bon pour ce genre de chose est Computational Geometry: Algorithms and Applications. Ils discutent à la fois du calcul du diagramme de Voronoï et de la méthode de la plaque trapézoïdale de l'emplacement ponctuel.

Si vous ne voulez pas faire le code vous-même, et vous ne devriez pas, alors essayez d'obtenir une bibliothèque comme CGAL qui fera la plupart du travail pour vous. Cela s'applique probablement aussi à la réponse de KD-tree, mais je ne le sais pas spécifiquement.

Answer 4

Vous avez besoin d'un spatial index.

Si vous obtenez le vôtre, vous pouvez faire bien pire que de choisir les algorithmes R-Tree ou Quad-tree.

Answer 5

Je voudrais aller avec un quadtree. C'est la structure spatiale la plus simple. En 2 dimensions, je recommande généralement quadtree au lieu de kd-tree, car c'est plus simple, plus rapide. Son inconvénient est plus la consommation de mémoire si le nombre de dimensions est élevé, mais dans le cas de 2 dimensions, la différence n'est pas significative.

Il y a une belle astuce d'optimisation si vos coordonnées sont en virgule flottante: Dans une requête, vous devrez d'abord trouver le nœud feuille qui contient le point auquel le point le plus proche est demandé. Pour ce faire, vous devrez aller dans l'arbre de la racine à la feuille - dans chaque itération de décider quel enfant-nœud à marcher sur. Stocker les identifiants/adresses des nœuds-enfants dans un tableau de taille 4 dans la structure Nœud. Numériser les coordonnées des points dans l'algorithme de requête. Ensuite, vous serez en mesure de trouver le sous-noeud approprié simplement en indexant le tableau par 2 bits propres des coordonnées du point numérisé. La numérisation est rapide: implémentez-la avec un static_cast simple.

Mais d'abord mettre en œuvre le quadtree sans optimisation, car il est facile de faire un bug avec les binaires opérations. Même sans cette optimisation, elle sera toujours la solution la plus rapide.