Discussion :

[comode]

Bonjour,

Imaginons une population d'éléments quelconques caractérisés par leurs identifiant unique et leurs coordonnées X et Y (non bornée).

Selon vous, quel serait la meilleur méthode pour déterminer (le plus rapidement possible) quels sont tous les éléments situés à une distance maximale x d'un élément donnée...

Alors évidemment, il existe la méthode fort peu subtile consistant à parcourir l'ensemble des éléments et récupérer ceux répondant à la formule :

x² < (Xelement2 -Xelement1)² + (Yelement2 - Yelement1)²

ce qui vous en conviendrez ne peut pas être utilisé sur un trop grand nombre d'éléments appelant eux même souvent cet algo...

Notez que la question n'est pas posé à titre de demande d'aide mais plutôt comme un défi... La structure de donnée utile pour stocker la liste de tous les éléments n'est donc pas imposée, et il est possible d'utiliser des arbres binaires, des tableaux hashés ou non, des liste chainées ou n'importe quoi d'autre, le tout étant de faire l'algo le plus rapide possible.

[Graffito]

il existe la méthode fort peu subtile ....

Ben, moi elle me plait bien, y'a vraiment pas grand chose à gagner à optimiser en éliminant par exemple les points tels que :
(Abs(Xelement2 -Xelement1)>x) OU (Abs(Yelement2 -Yelement1)>x)
d'ailleurs si la grande majorité des points sont concentrés dans un petit rayon, cette "optimisation" serait pénalisante.

[comode]

oui mais non... Cette méthode serait parfaitement inutilisable au delà d'un millier d'éléments a qui on demanderais de faire l'opération 2 ou 3 fois / secondes... Je donnais cet algo à titre d'exemple, mais c'est parfaitement irrecevable !

Perso, je pense à l'optimisation par un arbre binaire... Je découperai la surface sur laquelle se positionnent ces éléments en parcelles, et je stockerai les coordonnées X et Y de début de chaque parcelles dans 2 arbres binaires différents (1 arbre pour X, un arbre pour Y)... Ensuite, a chaque feuille de mes arbres binaires, j'associerai un tableau dynamique référençant les éléments dont la coordonnée concernée se situerai dans l'intervalle définie par cette feuille...

Ensuite, j'ai plus qu'a faire un algo de parcours de l'arbre pour récupérer les feuilles voisines (ce qui prendra une poignée d'instructions) contenant donc les références des éléments ayant des coordonnées voisines à la mienne. J'ai plus qu'a faire l'union des feuilles retournées par les arbres X et Y pour trouver tous les voisins, et appliquer ensuite l'ago sus-cité pour affiner mon résultat, et économiser des millions d'opérations par seconde.

Maintenant, la méthode est peut être plus délicate à mettre en oeuvre sur une surface non bornée, mais c'est le style de réponse que je m'attend à recevoir.

[Graffito]

Cette méthode serait parfaitement inutilisable au delà d'un millier d'éléments a qui on demanderais de faire l'opération 2 ou 3 fois / secondes...

Là, ca devient plus intéressant comme problème, puiqu'on a peut-être avantage à pré-traiter l'ensemble des éléments ou chaque élément quand on l'insère.
La solution dépendra :
- du nombre d'éléments total,
- du nombre d'éléments à traiter,
- du fait que la collection d'éléments soit variable ou fixe,
- et si la collection est variable, du taux de variation.

[comode]

éléments total : plusieurs dizaines de milliers
a traiter : tous et de façon désordonnée en temps et en ordre
collection variable dans le temps et l'espace (les éléments se déplacent et peuvent apparaitre ou disparaitre)
taux de variation faible en quantité, très importante en coordonnées

bref, un algo qu'on pourrait par exemple appliquer à une colonie de fourmis communiquant entre elles... Mais comme je disais, c'est pas une question posée dans le cadre d'un projet concret. Je le développerai surement pour le plaisir ensuite.

[Obsidian]

Le seul moyen d'optimiser un tel problème est de pouvoir trier les éléments selon un critère donné, voire les obtenir déjà triés et tâcher de maintenir cet ordre tout au long du traitement.

Dans le cas contraire, tu es obligé de tous te les palucher, pour la simple et bonne raison que tu ne peux déduire aucune information concernant un point à partir des points précédents. Sauf, bien sûr, à atteindre les limites du domaine de définition : si tu trouves un point confondu avec le point de référence, ce n'est plus la peine de chercher d'autres points plus proches, par exemple. Ce n'est donc pas applicables pour les points les plus éloignés.

J'avais eu le même problème en écrivant un petit simulateur de gravité : 300 étoiles qui interagissent toutes entre elles, ça fait 90 000 vecteurs à remettre à jour à chaque frame.

Une bonne manière d'optimiser les temps de traitement, en revanche, est d'utiliser le système approprié. Si tu passes en coordonnées polaires, par exemple, tu ne t'intéresse qu'à la distance et tu peux laisser l'angle de côté. Tu te retrouves alors avec un tableau à une dimension qu'il est très facile de trier et de maintenir classé. La recherche du premier est alors en O(1) : c'est le premier du tableau ! et la recherche d'un point quelquonque est en O(n log n).

Par contre, si tu as une idée dont la manière évoluent tes points au cours du temps, alors tu peux faire une présélection en te basant sur le fait que les autres points ne pourront pas surpasser les caractéristiques des premiers avant un nombre d'étapes donné.

Notez que la question n'est pas posé à titre de demande d'aide mais plutôt comme un défi.

Si c'est une manière de titiller les participants pour qu'il trouvent la solution à ta place sans que cela se voie, ça ne prend pas. Il y en a beaucoup qui ont essayé avant !

[pseudocode]

oui mais non... Cette méthode serait parfaitement inutilisable au delà d'un millier d'éléments a qui on demanderais de faire l'opération 2 ou 3 fois / secondes... Je donnais cet algo à titre d'exemple, mais c'est parfaitement irrecevable !

On peut se limiter a explorer les points qui sont "potentiellement" dans la boule de rayon R souhaitée.

En première approximation on peut éliminer tous les points qui ont une distance projetée sur X ou Y supérieure à R. Puis éliminer les points qui ne sont pas dans le carré de coté 2R. Et enfin éliminer ceux qui ne sont pas dans le cercle de rayon R.

Auquel cas, l'utilisation d'une segmentation d'espace 1D semble suffisante.

[comode]

On peut se limiter a explorer les points qui sont "potentiellement" dans la boule de rayon R souhaitée.

En première approximation on peut éliminer tous les points qui ont une distance projetée sur X ou Y supérieure à R. Puis éliminer les points qui ne sont pas dans le carré de coté 2R. Et enfin éliminer ceux qui ne sont pas dans le cercle de rayon R.

Auquel cas, l'utilisation d'une segmentation d'espace 1D semble suffisante.

Et comment tu fais pour éliminer tous les éléments qui ont une distance projetée sur X ou Y supérieure à R sinon en faisant une boucle qui parcourira l'ensemble des milliers d'éléments à chaque requête ?

[pseudocode]

Et comment tu fais pour éliminer tous les éléments qui ont une distance projetée sur X ou Y supérieure à R sinon en faisant une boucle qui parcourira l'ensemble des milliers d'éléments à chaque requête ?

Bah, tu maintiens tes éléments dans une structure de liste triée sur X (ou sur Y). Par exemple une liste chainée.

La recherche des bornes min/max de ton exploration se fait par une recherche dichotomique, donc assez rapidement. Reste a examiner les éléments entre ces 2 bornes.