Bonjour,

Je travaille sur un très grand cadrillage sur lequel sont disposés des pions au hasard. (éventuellement plusieurs par case) Etant donné :

  • Une case de la grille (x, y)
  • Une distance d


le problème est de trouver le plus rapidement possible la liste des pions situés à une distance (euclidienne) inférieure ou égale à d de la case donnée.

Code : Sélectionner tout - Visualiser dans une fenêtre à part
(a - x)² + (b - x)² < d²
Quelle structure de données utiliser pour coder l'ensemble des pions du damier ? Je ne cherche pas une complexité au pire minimum : en fait, la plupart du temps il y aura très peu de pions "visibles" depuis la case à la distance donnée. Pour cette raison, je ne peux pas me contenter de parcourir le domaine "visible" et regarder sur chaque case s'il y a des pions ou non.

Blustuff.