Bonjour,

Voici mon problème:
J'ai un tableau (tab1) contenant des dizianes de milliers de points (x,y,z). Pour chacun des points de tab1, je dois déterminer quel point est le plus près parmis un tableau (tab2) contenant lui aussi des dizaines de milliers de points (x,y,z). Les points de tab1 changent de position à chaque dt et dt>1000. Il faut donc un algo de recherche très rapide.

Présentement, j'utilise une recherche qui teste tous les points mais ce n'est vraiment pas assez rapide (en fait, j'utilise cette technique surtout pour tester les autres fonctionnalités de mon code). La création d'une structure de donnée sera donc nécessaire. Le problème est que je n'ai aucune idée laquelle utilisée.


J'ai trouvé que dans cette discussion il est question d'utiliser une structure de données géométrique du type quadtrees. Par contre, selon ma lecture rapide de documentation que j'ai trouvé, les quadtrees sont faits pour être utilisés sur un espace 2D, donc des points en (x,y) seulement. Existe-t-il une structure pour le 3D. Autres suggestions?

Merci!