Plus petit cercle circonscrit

[melgorien]

Bonjour,

J'ai un problème à résoudre.
J'ai les coordonnées de 10000 points sur excel, et j'ai besoin de trouver le plus petit cercle circonscrit de ces 10000 points.
Est-ce que vous auriez une idée de la manière de procéder pour arriver à ce résultat ?

Merci

[Jean_Luc]

Salut,

Une discussion intéressante sur le problême:

http://forums.futura-sciences.com/thread184758.html

Je n'ai pas tout lu encore, mais je pensais aussi que chercher
le plus petit traingle englobant tous les points pourrait peut
etre fournir la solution en prenant le cercle circonscrit.
Juste une idée

[Patastronch]

Salut,

Une discussion intéressante sur le problême:

http://forums.futura-sciences.com/thread184758.html

Je n'ai pas tout lu encore, mais je pensais aussi que chercher
le plus petit traingle englobant tous les points pourrait peut
etre fournir la solution en prenant le cercle circonscrit.
Juste une idée

Ca veut dire quoi le plus petit triangle ?

Intuitivement je dirais qu'il faut d'abord chercher l'enveloppe convexe de ton ensemble de point (y a des algo polynomiaux qui font ca si t'est en bicritère) et en déduire le diamètre du polygone convexe déduit (i.e: la plus longue distance entre 2 points de ton envelope convexe) qui sera alors le diametre de ton cercle dont le centre sera le milieu du diamètre de ton enveloppe.

Ensuitej'ai aucune idée de l'efficacité d'une telle manière de faire, mais je dirais que sur 10000 points bicritères ca devrait etre jouable.


Pour résumer, trouve la plus longue distance entre 2 points parmis ton nuage de points. Le cercle circonscrit sea alors de diamètre égale à cette distance et son centre sera au milieu du segment formé par ces 2 points.

[abcd22]

Bonjour,
Je dirais aussi qu'il faut commencer par calculer l'enveloppe convexe, mais ensuite les deux sommets les plus éloignés ne sont pas forcément les extrémités d'un diamètre du plus petit cercle circonscrit : sur un triangle ce n'est pas le cas, sauf cas particulier, en fait ce n'est meme pas sur qu'on obtienne un cercle circonscrit : prendre par exemple un triangle isocèle.

[Jean_Luc]

Ca veut dire quoi le plus petit triangle ?

Je voulais dire plus petite aire mais de toute façon ça marche pas.

Pour résumer, trouve la plus longue distance entre 2 points parmis ton nuage de points. Le cercle circonscrit sea alors de diamètre égale à cette distance et son centre sera au milieu du segment formé par ces 2 points.

[/quote]

Pour un ensemble de trois points formant un triangle équilatéral, il me semble
que ta méthode ne fonctionne pas.

[Patastronch]

Pour un ensemble de trois points formant un triangle équilatéral, il me semble
que ta méthode ne fonctionne pas.

Oui t'as raison, je suis allé trop vite. Je me pencherai sur la question ce week-end si je trouve un peu de temps. Par contre c'est pas un cercle circonscrit qu'on cherche, ca prete a ambiguité de dire ca, un cercle circonscrit a un polygone doit passer par tous les sommets e tla si je ne m'abuse vous cherchez le plus petit cercle qui englobe tous les points, ce qui est différent.

[Patastronch]

Bon on peut résumer le probleme à :
On cherche un point dans le plan qui minimise la distance maximale avec tous les autres sommets (facile a dire mais pas a faire), ce point sera alors le centre du cercle recherché et le rayon se ra cette distance maximale.

Pour chercher un tel point je serais tenté de dire qu'on peut y aller par recherche local car j'ai l'impression qu'il y a pas de minimum local mais seulement un minimum global. Si c'est bien le cas voila comment on peut faire :

On prend un point initiale quelconque, et on se rapproche du point le plus éloigné. La longueur maximale décroit alors. Des que cette longueur maximale croit, c'est qu'on est dans un minimum local => et donc global si l'hypothèse de départ est juste.

L'ennui avec cette méthode c'est le rapprochement qui doit se faire de manière discrète selon un pas fixé, ce qui implique que la solution trouvée a la fin sera une solution approximée et non optimale.

Peut etre y a t il une méthode analytique pour déterminer le point recherché? Ca serai plus beau, plus rapide, exacte et ca permetrait de se passer de l'hypothèse qu'un minimum est globale (car c'estpas dit que ce soit vrai), je continue à chercher :)

[Jean_Luc]

Bon on peut résumer le probleme à :
On cherche un point dans le plan qui minimise la distance maximale avec tous les autres sommets (facile a dire mais pas a faire), ce point sera alors le centre du cercle recherché et le rayon se ra cette distance maximale.

Tout à fait d'accord

Pour chercher un tel point je serais tenté de dire qu'on peut y aller par recherche local car j'ai l'impression qu'il y a pas de minimum local mais seulement un minimum global. Si c'est bien le cas voila comment on peut faire
...

Oui je pense que ton raisonement est tout à fait correct. Le probléme c'est
de determiner le point de départ pour la recherche. L'isobarycentre des points
me semble pas trop mal au moins si la répartition des points est uniforme.
Mais ce n'est hélas pas toujours le cas...

Peut etre y a t il une méthode analytique pour déterminer le point recherché? Ca serai plus beau, plus rapide, exacte et ca permetrait de se passer de l'hypothèse qu'un minimum est globale (car c'estpas dit que ce soit vrai), je continue à chercher

Oui en effet. Je ne connais pas la solution analytique. En tout cas, si elle
existe elle me permettrait de résoudre un problème pour un algorithme
de regroupement de points (collapse) et cela me serait trés utile.

Merci pour ton aide :we:

[Jean_Luc]

On peut alors prendre en compte seulement les points de l'enveloppe convexe, ça limitiré le nombre de boucles à faire.

Oui je pense que c'est un bonne idée de prendre en compte uniquement les
points de l'enveloppe convexe,mais néamoins, il faut considérer que la
détermination de l'enveloppe convexe se fait au mieux en nlog(n) avec
n=nombre de points. (si mes souvenirs sont bons).

[jver]

Tout à fait d'accord



Oui je pense que ton raisonement est tout à fait correct. Le probléme c'est
de determiner le point de départ pour la recherche. L'isobarycentre des points
me semble pas trop mal au moins si la répartition des points est uniforme.
Mais ce n'est hélas pas toujours le cas...



:we:

Supposons que tous les points soient alignés sur un axe.
Qu'il y en ait 1 au point 0, 1 au point 1000 et 998 au point 999.
Si tu prends le barycentre tu vas trouver, à peu près 999 et le diamètre de ton cercle va être de l'ordre de 1000; alors qu'un cercle centré en 500 et de rayon 500 suffirait.
Mais je n'ai pas tout suivi avec assez d'attention.

Enveloppe convexe, oui! Voir http://www.qhull.org

[Jean_Luc]

Oui, c'est bien ce que je dis, si la répartition des points est uniforme, l'isobarycentre devrait bien s'approcher de la solution. Mais dans le cas que tu décris, ce n'est pas le cas, la repartition n'est pas uniforme.
L'algorithme connu de Megiddo trouve la solution en temps linéaire (au moins dans le plan), c'est donc déja mieux que la calcul de l'enveloppe convexe.
J'aimerais savoir si l'on peut généraliser cet algo à .
(Minimal enclosing sphere)

[Patastronch]

Bon je repond un peu tard mais je pense avoir trouvé un algo qui fonctionne assez performant :

1. On démarre avec seulement 2 points, le cercle est alors evident.
2. On rajoute un point. Si ce point est dans le cercle précédent on change rien, sinon on cherche le point le plus éloigné de ce nouveau point et le diametre de notre cercle sera cette distance et son centre le milieu du segment formé par ces 2 points.
3. Si il reste des points non ajouté aller en 2 avec un de ces points. Sinon le dernier cercle trouvé est optimal.

A priori ca marche dans n'importe quelle dimension (pas que sur le plan) avec des hyperboule au lieu de cercle.
La compléxité est en O(n²). La preuve qu'il marche devrait se faire assez simplement par récurance je pense.


Edit : apres relecture mon algo ne marche pas, et je comrpends maintenant la subtilité de l'algo de Megiddo. Il faut non pas trouver le point le plus éloigné mais le cercle circonscrit le plus grand à trois points. Et ensuite en déduire si ce cercle est optimal ou pas. S'il ne l'est pas c'est qu'on peut tracer un cercle plus petit en prenant le centre d'un des coté du triangle de diametre la longueur du coté.

Voial comment adapter mon algo en utilisant la feinte de Megiddo :

1. On démarre avec seulement 3 points, le cercle est alors evident (cercle circonscrit a ces 3 points).
2. On rajoute un point. Si ce point est dans le cercle précédent on change rien, sinon on cherche le point le plus éloigné de ce nouveau point. On cherche ensuite un troisieme oint permetant d'avoir un cercle circonscrit de taille minimum englobant tous les points.
3. On vérifit si ce cercle est de taille minimal (en regardant si aucun des 3 cercles de diametre un de coté du triangle ne va). On selectionne le meilleur cercle parmis les 4 (le circonscrit et les 3 de diametre un coté)
4. Si il reste des points non ajouté aller en 2 avec un de ces points. Sinon le dernier cercle trouvé est optimal.

[Patastronch]

L'algorithme connu de Megiddo trouve la solution en temps linéaire (au moins dans le plan).

Je viens de lire son algo, c'est assez malin, mais c'est pas linéaire mais polynomiale : en O(n²)

[Patastronch]

Bon mon algo meme modifié ne marche pas tout court, le principe d'optimalité ne s'applique pas sur ce probleme (j'ai trouvé un contre-exemple), et on ne peut donc pas le faire de maniere itérative comme je le propose.

[Jean_Luc]

OK, merci pour tes efforts :lol3:

Je viens de lire son algo, c'est assez malin, mais c'est pas linéaire mais polynomiale : en O(n²)

Es-tu sur de ça ?
Je n'ai pas encore analysé et vérifié la complexité de la méthode prune-and-search que propose Megiddo.
As tu trouvé quelque chose qui contredit la complexité annoncée O(16n) ?

[Patastronch]

OK, merci pour tes efforts :lol3:



Es-tu sur de ça ?
Je n'ai pas encore analysé et vérifié la complexité de la méthode prune-and-search que propose Megiddo.
As tu trouvé quelque chose qui contredit la complexité annoncée O(16n) ?

Non en effet, c'est bien en temps linéaire, décidément je dis que des conneries aujourd'hui !

[frost]

J'avais pensé à un truc comme ça en lisant rapidement le problème mais je suis pas sûre que ce soit ce que tu cherche.

Je suis partie du fait que tes points sont sur un repère orthonormé. Alors ce que moi j'aurai fait c'est utilisé les x et les y des points pour calculer la distance des points par rapport au repère.
- Je prend le plus éloigné comme repère.
- Je prend ensuite le plus éloigné de celui là.
- Je calcule le point qui se trouve au centre du segment de droite que forme les deux.
- Je trace le cercle qui a pour centre ce point et pour diamètre la longueur du segment de droite.

Enfin, c'est comme ça que j'aurai fait mais je sais pas si ça répond à ta question et surtout si c'est bien ça qu'on t'a demandé comme réponse.

Les calculs sont assez simples, si t'as besoin de voir ce que ça donne, ou d'une feuille excell qui te montre les formules à mettre en place fait moi signe.

[Patastronch]

Si t'avais lu ce qui avait été dit tu aurais vu que ta méthode ne marche pas : par exemple pour 3 points formant un triangle équilatéral.

[frost]

Ah oui, c'est vrai. Je planche...

[Patastronch]

Ah oui, c'est vrai. Je planche...

Par contre je me demandais si cette méthode complété de :

Si tous les points ne sont pas dans le cercle, alors prendre le point le plus éloigné du centre de ce cercle et tracer le cercle circonscrit a ce point et aux 2 précédents.

A priori ca a l'air de marcher mais j'ai encore aucune idée de comment le prouver.

De toute facon une telle méthode est en O(n²) pour trouver les 2 premiers points les plus éloignés et est donc moins efficace que la méthode linéaire vu plus haut.