Trouver un sous-ensemble de points par distance relative

Question

J'écris un jeu dans lequel le joueur peut manipuler un grand nombre d'objets à la fois. Je voudrais que le joueur puisse sélectionner des objets en fonction des distances qui les séparent. Étant donné les emplacements de tous les objets, un objet de départ et un seuil de distance, quel est le moyen le plus rapide de trouver le sous-ensemble contenant l'objet de départ pour lequel la distance entre deux objets ne dépasse pas le seuil? Les solutions heuristiques sont parfaitement acceptables.

Answer 1

This library semble faire l'affaire.

« ANN est une bibliothèque écrite dans le langage de programmation C++ pour supporter à la fois exacte et rapprocher le plus proche voisin chercher dans les espaces de différentes dimensions

[...] Dans le problème du plus proche voisin, on donne un ensemble P de points de données dans un espace de dimension D. Ces points sont prétraités dans une structure de données, de sorte que, en fonction de n'importe quel point q, les points de P à q peut être rapporté efficacement. "

Answer 2

Dépend de votre structure de données. Principalement, vos objets sont-ils déjà triés/partitionnés par la distance? Je ne peux pas penser à une heuristique à distance ... mais vous pourriez certainement le faire en parallèle, ce qui devrait aider.