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

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 critique en termes de performances pour résoudre ce problème? La liste des points ne va pas changer; ce qui signifie que je n'ai pas besoin d'effectuer d'insertion ni de suppression. Je veux juste trouver le voisin le plus proche d'une cible xq, yq point dans cet ensemble.

Modifier 1: Merci à tous! Comme Stephan202 l'a bien deviné, 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 la trier).

Je construirai une fois la structure de données sur la base de la liste, puis j'utiliserai cette structure de données générée dans la fonction (si ce processus 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 j’ai le sentiment que c’est le cas. Je mettrai à jour les résultats lorsque j’aurai des résultats pertinents).

Éditer 2: J'ai constaté que ce problème s'appelle "voisin le plus proche"!

Éditer 3: le premier titre était "À la recherche d'un algorithme (pour la recherche spatiale et l'indexation spatiale) (voisin le plus proche)"; J'ai choisi un nouveau titre: "Meilleur algorithme critique pour la résolution du 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 à un nouveau point (qui ne sera pas inséré), j’ai choisi de travailler (actuellement) sur KD-Trees. Merci à tous!

Answer 1

Comme l'a noté Stephan202, si vous envisagez 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 packages tels que OpenCV 2.0 . Ou vous pouvez en implémenter un vous-même!

MODIFIER: j'avais posé une question sur les implémentations de kd-tree ici - pourrait être utile.

EDIT: Les arbres KD ont été largement utilisés avec succès pour les recherches NN :) - De plus, si vous souhaitez accepter des correspondances approximatives, vous pouvez utiliser Bibliothèque rapide pour le plus proche voisin (FLANN) . L’implémentation FLANN est présente dans OpenCV 2.0 .

Si vous ne voulez pas de réponses approximatives, vous pouvez modifier les paramètres FLANN pour effectuer une recherche dans tout l'arborescence.

Answer 2

Si le point de requête (xq, yq) varie et que la liste ne change pas, vous devez calculer le Diagramme de Voronoï de la liste des points. Cela vous donnera un ensemble de polygones ou "cellules". (dont certains sont infinis); chaque polygone correspond à un point de la liste d'origine, appelé le "site" de cette cellule. Tout point qui se trouve 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 situé sur une limite entre deux polygones est à égale distance de chaque site.

Une fois que vous en êtes arrivé là, vous avez besoin d’un moyen simple de déterminer le polygone dans lequel vous vous trouvez. C’est ce que l’on appelle le problème de localisation de point .

Un Géométrie numérique: algorithmes et applications constitue un très bon livre pour ce genre de choses. . Ils discutent en détail du calcul du diagramme de Voronoï et de la méthode de localisation des points trapézoïdale.

Si vous ne voulez pas créer le code vous-même et que vous ne devriez pas le faire, essayez d’obtenir une bibliothèque du type CGAL qui effectuera la majeure partie du travail à votre place. Ceci s’applique probablement aussi à la réponse de KD-tree, mais je ne le sais pas spécifiquement.

Answer 3

Vous avez besoin d'un index spatial .

Si vous faites le vôtre, vous pouvez faire bien pire que de choisir R-Tree ou algorithmes à quatre arbres .

Answer 4

J'irais avec un quadtree. C'est la structure spatiale la plus simple. En 2 dimensions, je recommanderais généralement quadtree au lieu de kd-tree, car il est plus simple, plus rapide. Son inconvénient est une consommation de mémoire supérieure si le nombre de dimensions est élevé, mais dans le cas de deux dimensions, la différence n’est pas significative.

Il existe un bon truc 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’arborescence de la racine à la feuille - à chaque itération, en décidant du nœud enfant sur lequel marcher. Stockez les identifiants / adresses des noeuds enfant dans un tableau de 4 tailles dans la structure du noeud. Numérisez les coordonnées du point dans l'algorithme de requête. Ensuite, vous pourrez trouver le sous-nœud approprié en indexant simplement le tableau par 2 bits appropriés des coordonnées numérisées du point. La numérisation est rapide: implémentez-la avec un simple static_cast.

Mais d'abord, implémentez le quadtree sans optimisation car il est facile de créer un bogue avec les opérations sur les bits. Même sans cette optimisation, ce sera toujours la solution la plus rapide.

Answer 5

Parcourez chaque autre point en utilisant la formule de distance pour trouver la distance minimale à partir de Q (xq, yq).

Cependant, vous n'avez pas fourni suffisamment d'informations pour une réponse critique en termes de performances.

Par exemple, si Q est un point TRÈS commun, vous pouvez calculer la distance qui le sépare de Q et l’enregistrer avec chaque point.

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