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

Question

Quel est le moyen le plus rapide de trouver le point le plus proche du 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 de point (x_p, y_p, z_p). Comment trouver le point le plus proche dans A à (x_p, y_p, z_p) ?

Pour autant que je sache, la manière la plus lente de le faire est d'utiliser la recherche linéaire. Y a-t-il de meilleures solutions ?

L'ajout d'une quelconque structure de données auxiliaire est possible.

Answer 1

Vous pouvez organiser vos points dans un Octree. Ensuite, vous n'avez qu'à rechercher un petit sous-ensemble.

Un Octree est une structure de données assez simple que vous pouvez implémenter vous-même (ce qui serait une expérience d'apprentissage précieuse), ou vous pouvez trouver des bibliothèques utiles pour vous aider à démarrer.

Answer 2

Je suggère que KD-tree fonctionne bien. Également bon pour les recherches de voisins les plus proches.

Answer 3

J'utiliserais un arbre KD pour le faire en temps O(log(n)), en supposant que les points soient distribués aléatoirement ou que vous ayez un moyen de maintenir l'équilibre de l'arbre.

http://fr.wikipedia.org/wiki/Kd-tree

Les arbres KD sont excellents pour ce type de requête spatiale, et vous permettent même de récupérer les k voisins les plus proches d'un point de requête.