Quel est le moyen le plus rapide pour trouver le point le plus proche d'un point donné?

Quel est le moyen le plus rapide pour trouver le plus proche point à point donné dans le tableau de données?

Par exemple, supposons que j'ai un tableau A de points 3D (avec les coordonnées x, y et z, comme d'habitude) et le point (x_p, y_p, z_p). Comment puis-je trouver le point le plus proche dans A à (x_p, y_p, z_p)?

Autant que je sache, la plus lente façon de le faire est d'utiliser la recherche linéaire. Sont-il de meilleures solutions?

Ajout de tout un auxiliaire de la structure de données est possible.

InformationsquelleAutor qutron | 2010-12-03
  1. 25

    Vous pouvez organiser vos points dans un L'Octree. Ensuite, vous avez seulement besoin de chercher un petit sous-ensemble.

    Un Octree est assez simple structure de données, vous pouvez mettre en œuvre vous-même (ce qui serait une précieuse expérience d'apprentissage), ou vous trouverez peut-être utile de bibliothèques pour y arriver.

    • Les algorithmes proposés sont efficaces seulement si nous avons besoin à plusieurs reprises de recherche d'un plus proche voisin pour un grand nombre de points. Si nous avons juste besoin de l'information pour un point, un linéaire de recherche est plus efficace.
    • L'élaboration sur mon commentaire, la construction de l'arbre lui-même (KD Tree ou OC Arbre) sera pire que linéaire. Je ne suis pas sûr d'OC arbres, mais KD Arbres de prendre en O(NlogN). Par conséquent, pour une seule requête d'une recherche linéaire est mieux.
    • Mais vous connaître quel est le coût de calcul des centaines de milliers de multiplcations seulement pour kNN d'un seul point?Cela pourrait être réduite à peu de calcul de la distance dans l'Octree et le coût de construction d'un octree est beaucoup moins que la surcharge de nombreuses multiplications dans le calcul de la distance linéaire moteurs de recherche, même pour un seul point car de nos jours, point de nuage est facilement assez grand pour avoir plus de 100k points.
    InformationsquelleAutor dkamins
  2. 16

    Si vous êtes en train de faire une fois plus proche voisin de la requête, puis une recherche linéaire est vraiment le meilleur que vous pouvez obtenir. C'est bien sûr en supposant que les données n'est pas pré-structuré.

    Toutefois, si vous allez faire beaucoup de requêtes il y a quelques l'espace de partitionnement de structures de données.Ces prenez le prétraitement à la forme de la structure, mais on peut ensuite répondre le plus proche voisin des requêtes très rapide.

    Puisque vous faites affaire avec de l'espace 3D, je vous recommande de regarder soit octrees ou kd-trees. Kd-trees sont plus génériques (ils travaillent pour arbitraire dimensions) et peut être rendue plus efficace que les octrees si vous convient de mettre en œuvre un algorithme d'équilibrage (par exemple, la médiane fonctionne bien), mais octrees sont plus faciles à mettre en œuvre.

    ANN est une grande bibliothèque à l'aide de ces structures de données, mais aussi en permettant approximative voisin le plus proche, les requêtes qui sont beaucoup plus rapides, mais ont une petite erreur car ils sont seulement des approximations. Si vous ne pouvez pas prendre toute erreur, définissez l'erreur liés à 0.

    InformationsquelleAutor marcog
  3. 4

    Je suggère KD-arbre, beau travail. Aussi bon pour voisin le plus proche de recherches.

    InformationsquelleAutor Vedang Joshi