C++ Girl
  1. C++ Girl
  3. Tous les k voisins les plus proches en 2D, C ++
Intereting Posts
FILETIME à __int64 Commentaires sur le fichier .pro Qt Creator Erreur: nvlink error: référence non définie à ‘_ZN8Strategy8backtestEPddd’ “ Convention de style C ++: noms de parameters dans la déclaration de classe stack au format clang tous les arguments if-statement s’ils sont trop longs std :: queue <T, liste > :: size () est lent dans O (n)? Pourquoi le renvoi d’une référence à une variable automatique fonctionne-t-il? Création d’une bibliothèque CUDA statique à associer à un programme C ++ Simulation du mldivide de matlab avec OpenCV L’algorithme récursif de sous-chaîne ne fonctionne pas Créer un sous-tuple à partir d’un std :: tuple L’appel de asio io_service poll () ou poll_one () de manière nestede ou récursive (c’est-à-dire dans un gestionnaire) est-il valide? C ++ binary en décimal Erreurs LNK2001 et LNK2019 – Symboles externes non résolus dans DirectX Comment encoder une vidéo à partir de plusieurs images générées dans un programme C ++ sans écrire les images séparées sur un disque?

Tous les k voisins les plus proches en 2D, C ++

Je dois trouver pour chaque sharepoint l’dataset tous ses voisins les plus proches. L’dataset contient env. 10 millions de points 2D. Les données sont proches de la grid, mais ne forment pas une grid précise …

Cette option exclut (à mon avis) l’utilisation des arbres KD, où l’hypothèse de base est qu’aucun point n’a la même coordonnée x et la coordonnée y.

J’ai besoin d’un algorithme rapide O (n) ou supérieur (mais pas trop difficile à mettre en œuvre :-))) pour résoudre ce problème … En raison du fait que boost n’est pas normalisé, je ne souhaite pas l’utiliser …

Merci pour vos réponses ou des exemples de code …

Je voudrais faire ce qui suit:

  1. Créez une grid plus grande au-dessus des points.

  2. Parcourez les points linéairement et, pour chacun d’eux, déterminez la grande “cellule” à laquelle elle appartient (et ajoutez les points à une liste associée à cette cellule).

    (Cela peut être fait en temps constant pour chaque point, il suffit de faire une division entière des coordonnées des points.)

  3. Maintenant, parcourez à nouveau les points linéairement. Pour trouver les 10 voisins les plus proches, il suffit de regarder les points des cellules adjacentes plus grandes.

    Étant donné que vos points sont répartis de manière à peu près égale, vous pouvez le faire dans le temps proportionnellement au nombre de points dans chaque (grande) cellule.

Voici une image (laide) décrivant la situation:

entrez la description de l'image ici

Les cellules doivent être suffisamment grandes pour (le centre) et les cellules adjacentes pour contenir les 10 points les plus proches, mais suffisamment petites pour accélérer le calcul. Vous pourriez le voir comme une “fonction de hachage” où vous trouverez les points les plus proches dans le même seau.

(Notez que, à proprement parler, ce n’est pas O (n), mais en modifiant légèrement la taille des plus grosses cellules, vous devriez vous approcher suffisamment. 🙂

J’ai utilisé une bibliothèque appelée ANN (voisin approximatif approximatif) avec un grand succès. Il utilise une approche Kd-tree, bien qu’il y ait plusieurs algorithmes à essayer. Je l’ai utilisé pour localiser des points sur une surface sortingangulée. Vous pourriez avoir de la chance avec ça. Il est minimal et facile à inclure dans ma bibliothèque en déposant simplement son code source.

Bonne chance pour cette tâche intéressante!