Discussion :

[goast]

Bonjour,
Je cherche un algorithme qui permet pour un ensemble de points mobiles de trouver un groupe de points situés à l'intérieur d'un cercle de rayon fixe.
Pour l'instant je n'ai trouvé aucune piste
Quelqu'un a une idée?

Merci d'avance

[Invité]

Bonjour,
Je cherche un algorithme qui permet pour un ensemble de points mobiles de trouver un groupe de points situés à l'intérieur d'un cercle de rayon fixe.
Pour l'instant je n'ai trouvé aucune piste
Quelqu'un a une idée?

Merci d'avance

Euh? Calculer la distance entre les points et le centre du cercle?

Ou plus précisément le carré de celle ci, pour éviter de calculer la racine.
Et, pour gagner du temps, inscrire le cercle dans un carré, et éliminer les points qui sont en dehors?

Francois

[goast]

mmm desolé je me suis mal exprimé :s
En fait j'ai un ensemble de points qui bougent.
Quand 5 de ces points se rapprochent et qu'on peut trouver un cercle (de rayon R prédéfini) qui englobe les points je doit faire un traitement.
Donc du coup je ne connais pas le centre du cercle

Des idées?
Merci

[Invité]

Des idées?

Une méthode générale pour trouver le rayon minimal d'un cercle contenant n points... (joli article, soit dit en passant : il ne contient pas une formule...)

http://archive.numdam.org/ARCHIVE/BS..._13__198_0.pdf

A priori, la méthode serait donc de répéter cela pour tous les groupes de 5 points de ton ensemble, et vérifier que le rayon du cercle minimal est inférieur ou égal à R...

En fait, tu vas utiliser des heuristiques pour éviter une partie de ces calculs...

En gros : deux points séparés de plus de 2R ne peuvent être dans le même cercle de rayon R, tu cherches donc les familles de 5 points dont les distances prises 2 à 2 sont toutes inférieures ou égales à 2R, et tu appliques l'algorithme... Si tu as beaucoup de points, qui ne bougent pas trop vite, un kd-tree serait probablement la bonne structure, mais s'ils bougent vite, des heuristiques un peu rusées fonctionneront probablement mieux.

Francois

[goast]

Merci fcharton
Je vais etudier cet article.
Mais pour l'instant j'utilise une méthode qui ne donne pas exactement ce que je veux mais le resultat est satisfaisant pour l'instant.
En fait je crée des groups de points.
Un point est ajouté à un groupe s'il est à une distance plus petite que R d'un des points d'un groupe deja existant...