Discussion :

[Blustuff]

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.

[Matthieu Brucher]

Ce que tu pourrais faire, c'est faire du hiérarchique : tu découpe ton plan en cases, et tu surveilles juste quels points sont dans quelle case - on fait ça pour les jeux vidéos pour al collision par exemple et aussi la vision -, ...
Quand tu veux voir si un point est proche ou pas, tu prends les cases autour du point et tu parcours les éléments dans les cases.

[Blustuff]

C'est ce que je fais actuellement. Mais ça me pose des problèmes. En particulier la question : "Quelle taille de case prendre ?"

[Matthieu Brucher]

Ca, c'est un gros problème ! Plus les cases sont petites, moins elles sont utiles, et plus il y a de changement de région. Plus les cases sont grandes, plus il y a d'éléments. Le mieux, tester pour voir les paramètres optimaux.

[Graffito]

Bonjour,

En prenant comme dimension des cotés des "super-cases" la racine du nombre de cases du quadrillage, on devrait être proche de la bonne valeur.

Si on fait un découpage à deux niveaux, "super-cases" et "hyper-cases", on utiliserait la racine cubique.

[Blustuff]

Pourquoi la racine carrée ? Pourquoi faire un double découpage ?