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 :
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...x² < (Xelement2 -Xelement1)² + (Yelement2 - Yelement1)²
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.
Partager