Algorithme efficace pour la recherche de coordonnées 3D dans un tableau

J’ai un grand tableau (> 10 ^ 5 entrées) de coordonnées 3D r = (x, y, z), où x, y et z sont des flottants. Quel est le moyen le plus efficace de rechercher une coordonnée donnée r ‘dans le tableau et de lui donner un index. Notez que le r ‘peut ne pas être donné avec la même précision que r; Par exemple, si le tableau a des coordonnées stockées (1.5, 0.5, 0.0) et que r ‘est donné par (1.49999, 0.49999, 0.0), l’algorithme doit correctement choisir la coordonnée. Je développe le code en C.

Comment peut-on utiliser la capacité de recherche O (1) de la table de hachage à cette fin? La conversion de la coordonnée en chaîne est hors de question en raison d’un problème lié à la précision. Existe-t-il une structure de données particulière qui aiderait dans l’algorithme O (1)?

Merci

OnRoadCoder

vérifie R-trees , déjà implémenté sur certains SGBDR, comme SQLite, et (je pense) Postgres

Pour effectuer une recherche “floue” comme vous le décrivez (afin que vous puissiez prendre en charge de légères inexactitudes), vous devrez sacrifier les algorithmes O (1).

Cela étant dit, il existe de très bons algorithmes pour cela. Le partitionnement d’espace (comme l’utilisation d’un octree ou d’un arbre KD ) est une option courante et répandue.

Si la plage de valeurs est limitée, choisissez la précision souhaitée. Maintenant, la clé (1,2,3) pointera vers une liste chaînée (ou une structure de données plus sophistiquée) de tous les points qui se trouvent dans Manhattan. Distance de 3 * d (d = 0,5? – dépend des détails) à partir de (1, 2,3). Vous connaissez mieux votre application, vous pouvez donc choisir plus facilement d. L’approche d’optimisation dépend de la manière dont les données sont dissortingbuées.

MODIFIER:

La faiblesse ici est que si plusieurs points sont concentrés dans un même cube, il est très difficile d’utiliser une table de hachage pour garantir O (1) … plutôt comme O (n) 🙂

Une sorte de structure de données arborescente peut garantir O (log n).

Ce que vous demandez ressemble à la recherche du plus proche voisin . Une approche pourrait consister à coder une arborescence kd (ou toute technique utilisant une partition d’espace) et à l’utiliser pour trouver le point le plus proche de votre requête. Mais vous pouvez également opter pour une approche basée sur le hachage , qui correspond essentiellement à la réponse d’Ipthnc, tout en essayant d’éviter de mauvaises performances pour les cas dégénérés.