La mise en œuvre efficace du plus Proche Voisin de Recherche

Je suis en train de mettre en œuvre un algorithme efficace pour le plus proche voisin de recherche problème.

J'ai lu des tutoriels à propos de certaines structures de données, les opérations de soutien pour ce genre de problème (par exemple, R-tree, couvercle arbre, etc.), mais tous sont difficiles à mettre en œuvre.

Aussi je ne peux pas trouver un exemple de code source pour ces structures de données. Je sais que C++ et je suis en train d'essayer de résoudre ce problème dans cette langue.

Idéalement, j'ai besoin de liens qui expliquent comment mettre en œuvre ces structures de données à l'aide du code source.

Quelle est la dimension de vos données? Pour la 2D de données de point de je vous conseille d'utiliser un Kd-tree. Il est facile à mettre en œuvre. Pour d'autres types de données/géométries, vous voudrez peut-être regarder à la R-arbres (boost 1.54 prend en charge rtree index)

OriginalL'auteur dato datuashvili | 2012-04-06

  1. 2

    Vous pouvez essayer un linesweep algorithme pour trouver le plus proche de la paire de points: http://community.topcoder.com/tc?module=Static&d1=tutoriels&d2=lineSweep.

    OriginalL'auteur Bytemain

  2. 11

    Il y a plusieurs bons choix de rapide la plus proche voisin de recherche des bibliothèques.

    • ANN, qui est basé sur les travaux de Montage et Arya. Ce travail est documenté dans un article de S. Arya et D. M. du Mont. "Se rapprocher du voisin le plus proche des requêtes dans des dimensions fixes". Dans Proc. 4ème ACM-SIAM Sympos. Discret Algorithmes, pages 271-280, 1993.

    • FLANN, qui est basé sur les travaux de Marius Muja & Co. Il y a un papier par Marius Muja et David G. Lowe, "Fast Approximative de plus proches Voisins avec un Algorithme Automatique de Configuration", dans la Conférence Internationale sur la Vision par Ordinateur la Théorie et Applications (VISAPP'09), 2009. Le code de FLANN est disponible sur github

    FLANN semble être plus rapide dans certains cas, et est une version plus moderne de la code avec de solides liaisons pour un certain nombre d'autres langues, qui peuvent apporter des modifications rapidement. ANN est sans doute un bon choix si vous voulez une solide bien testé la bibliothèque standard.

    Modifier en Réponse au Commentaire

    Ces deux bibliothèques ont une vaste documentation et des exemples.

    Exemple de code pour l'ANN est disponible dans le Manuel, Dans la section 2.1.4

    Exemple de code pour FLANN est disponible dans le FLANN référentiel exemples répertoire, par exemple /exemples/flann_examples.c

    comment l'utiliser,quand, par exemple, j'ai (x1,y1)(x2,y2)...(xn,yn)?
    la réponse a été mis à jour pour inclure des liens à des exemples de chacun des projets de la documentation.
    j'ai besoin d'instal oui FLANN bibliothèque?
    Oui, vous le feriez. À l'aide de FLANN (ou ANN) exige que vous les fichiers disponibles sur votre de les inclure et de la bibliothèque des chemins, de la même manière que vous le feriez avec tout autre non-trivial de la bibliothèque C++
    Pourriez-vous ajouter des nanoflann pour la réponse? C'est un fork de FLANN et apparemment plus rapide. C'est un C++11-tête de la seule bibliothèque qui est vraiment pratique. Merci et salutations

    OriginalL'auteur Andrew Walker