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 ?

[Matthieu Brucher]

C'est une valeur heuristique, empirique, c'est tout

[Graffito]

Bonjour,

Pourquoi la racine carrée ?

La racine carrée équilibre le nombre de recherches sur les cases et les super cases.
Exemple, si le quadrillage comporte 256x256 cases, on aura 16x16 supercases comportant chacune 16x16 cases.

Pourquoi faire un double découpage ?

Exemple le quadrillage comporte 1000x1000 cases, on aura 10x10 hypercases contenant chacune 10x10 supercases comportant chacune 10x10 cases.

Ainsi on peut lorsqu'il y a peu de cases remplies éliminer rapidement les hypercases sans rien, sinon dans les hypercases avec qqchose on élimine vite les supercases vite.

[Blustuff]

L'indexation des super-cases est naturelle. On trouve en O(1) les super cases à tester. Si la taille des cases est bien choisie en fonction des "d" donnés, on a que quatre super cases à tester au maximum, une au minimum.

Je ne vois pas encore l'utilité d'équilibrer les recherches sur les cases et super-cases, ou d'éliminer les hyper cases.

[Médiat]

Tu peux aussi passer par une autre distance :

Max(Abs(x-a), Abs(y-b)) <= racine((x-a)²+(y-b)²)

Or la détermination des points tels que Max(Abs(x-a), Abs(y-b)) < d est rapide, puisque cette recherche est facilement indexable

[Blustuff]

Comment est elle indexable ?

(Je viens de comprendre ce que signifie l'équilibrage de la recherche sur les cases et super cases. Mais en l'occurence, mon problème est un peu plus restreint : je sais que d ne bougera pas beaucoup et son encadrement. Mon interrogation reste alors entière puisqu'on sait qu'en choisissant bien la taille des super cases il n'est pas nécessaire de faire de recherche sur l'ensemble des super cases. Est-ce un bon choix ?)

[Médiat]

Comment est elle indexable ?

Tu connais tes points, tu peux donc les indexer suivant x et y, or chercher des points tels que abs(x-a) < d reviens à chercher des points tels que
a - d <= x <= a + d, l'index sur x pourra être utilisé (même chose en y)

[Blustuff]

Le titre du sujet est "index dans le plan", certes. On pense qu'à partir d'un point du plan, on peut trouver facilement les points autour. En fait non, et si j'ai bien compris votre logique, vous proposez de par exemple d'abord parcourir les x proches, et pour chaque x, parcourir les y proches : Ce qui revient à parcourir toute le zone visible ce que je ne veux pas :

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.

Si je me trompe, éclairez moi.

[Graffito]

Bonjour,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

il n'est pas nécessaire de faire de recherche sur l'ensemble des super cases.

En effet, il faut seulement tester les supercases situées autour du point de test. Si d est la distance recherchée et si la diagonale d'une supercase est D, on peut éliminer toutes les cases dont la distance de leur centre au centre de la supercase contenant le point de test est supérieur à d+D .

[Blustuff]

Oui, ça je sais puisque c'est exactement la méthode que j'emploie actuellement. Mais ça ne répond pas à ma question.

[Graffito]

Bonjour,

Je ne sais pas si ça répond à la question, mais pour utiliser le découpage de l'espace, il faut gérer, en parallèle avec le tableau des coordonnées des pions, une liste chainée permettant de parcourir la liste des pions de chaque supercase.

[Blustuff]

Non. Ma solution marche : Je cherche une autre solution.

[Matthieu Brucher]

Ah, OK
Ben, je ne sais pas si ça existe vraiment

[Blustuff]

J'avais pourtant une idée qui doit marcher, de créer et de maintenir un graphe, où les noeuds sont les cases occupées d'où partent quatre arcs (liste quadruplement chainée ?) pour parcourir de proche en proche. On a un algorithme très rapide pour trouver les pions proches d'une case déjà occupée, mais je n'ai pas d'algorithme efficace pour maintenir le graphe en cas de déplacement d'un pion sur le damier.

[Fladnag]

(coucou Blustuff ;o)

dans le cas du graphe, lors d'un déplacement, il faut mettre a jour les arcs du points déplacés ET des points liés

Dans tout les cas, je pense a un algo de recherche de proche en proche a partir des anciens arcs.

Par exemple, si on s'est déplacé d'une position vers le haut :

* l'arc du bas ne devrait pas avoir changé (a moins qu'on ait depassé le point lié a l'arc du haut, dans ce cas l'arc du haut devient l'arc du bas pour les 2 points qui se sont croisés)
* L'arc du haut ne devrait pas avoir changé (sauf cas exposé ci dessus, dans ce cas là, on echange les arcs a nouveau)
* L'arc de droite peut avoir changé, il faut comparer les distances entre le point lié a l'arc de droite et le point lié a l'arc du haut de l'arc de droite (voir suivre un chemin (comme lorsqu'on suit le mur de gauche d'un labyrinthe) jusqu'a ce qu'on arrive a un point plus éloigné que l'ancien point ou que l'arc du haut)
* idem pour l'arc de gauche

Les seuls algos demandant une recherche plus globale sur la carte seraient les cas d'insertion de nouveaux points sur la carte.