Plus petit cercle circonscrit

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: 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


Posted by: 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


Posted by: Patastronch

Citation:
Posté par 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


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.


Posted by: 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.


Posted by: Jean_Luc

Citation:
Posté par Patastronch
Ca veut dire quoi le plus petit triangle ?


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

Citation:
Posté par Patastronch
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.


Posted by: Patastronch

Citation:
Posté par Jean_Luc
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.


Posted by: 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 :)


Posted by: melgorien

Oui, je suis d'accord avec toi l'appellation "plus petit cercle circonscrit" porte à ambiguité. Donc c'est bien le plus petit cercle contentant tous les points que je recherche.
J'ai un peu étudié la question mais ça reste de l'autre du théorique et en plus je ne suis pas du tout un spécialiste en mathématique, mais j'aimerai que vous me donniez votre avis dessus quand même :

Il faut que l'aire du cercle soit à la fois la plus petite possible et contienne les 10000 points.
Donc j'ai réfléchi au système suivant :
1- prendre trois points quelconques (on incrémente petit à petit les coordonnées X et Y des points afin de tous les faire)
2- créer le cercle qui passe par ses trois points
3- est-ce que les 10000 points sont dans le cercle ?
- NON : revenir à l'étape 1
- OUI : passer à l'étape 4
4- calculer l'aire du cercle associé aux 3 points
5- mémoriser l'aire ds l'emplacement 1
5- est-ce que l'aire est plus grande que celle enregistrer précédemment (mémoriser dans l'emplacement 2) ?
- OUI : revenir à l'étape 1
- NON : passer à l'étape 6
6 - enregistrer l'aire et les coordonnées des 3 points dans l'emplacement 2
... recommencer les étapes jusqu'à avoir parcourue toute les possibilités.

Problème, il y a 10000 points, donc ça risque d'être extrémement long à calculer. On peut alors prendre en compte seulement les points de l'enveloppe convexe, ça limitiré le nombre de boucles à faire.
Bien sur, il peut s'avérer que le plus petit cercle passe seulement par 2 points, mais ça serait quand même une très bonne approximation de supposer qu'il passe par 3 des points ?

Je vous laisse réagir là dessus !


Posted by: Jean_Luc

Citation:
Posté par 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.


Tout à fait d'accord :)

Citation:
Posté par Patastronch
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...

Citation:
Posté par Patastronch
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


Posted by: Jean_Luc

Citation:
Posté par melgorien
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).


Posted by: jver

Citation:
Posté par Jean_Luc
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...


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 www.qhull.org


Posted by: 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 à \mathbb{R}^3.
(Minimal enclosing sphere)


Posted by: 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.


Posted by: Patastronch

Citation:
Posté par Jean_Luc
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²)


Posted by: 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.


Posted by: Jean_Luc

OK, merci pour tes efforts

Citation:
Posté par Patastronch
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) ?


Posted by: Patastronch

Citation:
Posté par Jean_Luc
OK, merci pour tes efforts



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 !


Posted by: 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.


Posted by: 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.


Posted by: frost

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


Posted by: Patastronch

Citation:
Posté par frost
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.


Posted by: Jean_Luc

Ce n'est pas bête du tout !
Mais cela supposerait que si le cercle (de diamètre formé par les 2 points les plus éloignés) contient tout les points alors ce cercle serait solution et l'on ne pourrais pas trouver de cercle plus petit.
Mème si la complexité de cette méthode n'est pas linéraire, au moins il est bcp plus facile de la généraliser à R^n.
Reste encore à vérifier que ça marche...


Posted by: Imod

Je m'excuse de m'éloigner du sujet mais dans le dernier "Dossier pour la science" , il y a toute une série de procédés "Physique" qui permettent de résoudre instantanément des problèmes extrèmement complexes mathématiquement . Avec des élastiques : enveloppe convexe , droite de régression , classement avec des spaghettis , surface minimale avec une bulle de savon , puissance quatrième avec une poutre ...

On pourrait imaginer un cerceau se contractant sur les points ( mais ce n'est plus des maths ) .

Imod










-