Cercle circonscrit à un nuage de plan

[Nicolas666666]

Bonjour à tous!
Voilà, je me lance dans un rapport qui se rapporte à la science des matériaux et aux plans de cissaillement..
J'arrive au point où j'ai besoin de connaitre le plus petit cercle cisconscrit à un nuage de points, tout ceci sous excel.
Ma première idée est de poser l'équation d'un cercle
et d'essayer d'inclure sous formes d'équations le fait que tous les points doivent êtres contenus dans ce cercle.. Qu'en pensez-vous?
Avez vous d'autres idees?
Cordialement, et merci d'avance!
-----

[invite986312212]

bonjour,

il y a des algorithme pour déterminer l'enveloppe convexe d'un ensemble fini de points du plan. J'en ai programmé un sous R, je peux éventuellement te fournir la fonction mais je ne sais pas si c'est facile à traduire en langage excel. Ensuite, pour passer de l'enveloppe au cercle, je ne sais pas faire, mais je pense que au moins deux sommets de l'enveloppe convexe (qui est un polygone convexe) appartiennent au cercle circonscrit, et les points intérieurs à l'enveloppe convexe ne jouent aucun rôle, donc ça te fera déjà moins d'équations.

[Nicolas666666]

Merci de ton aide (un peu compliqué pour moi pour le moment, du moins j'ai lu entre les lignes car je suis un peu pressé au moment de répondre, je m'y repenche un peu plus tard)
Rapidement j'ai pensé à une autre méthode : je cherche le centre du cercle :
X mon centre, mes points, je cherche la distance entre tous les points et le centre et je cherche à minimiser cette fonction, qu'en pensez-vous?
Et pour le rayon, simplement la distance du point le plus éloignée de mon centre..
Cordialement

[invite986312212]

si au lieu de minimiser la somme des distances, tu veux minimiser la somme des carrés des distances, alors il y a une solution explicite: c'est le barycentre des points (la moyenne en d'autres termes). Ca peut être une solution approchée pas trop mauvaise, mais je ne crois pas que ça te donne le plus petit cercle. Déjà, la moyenne des sommets de l'enveloppe convexe doit être meilleure.

[A voir en vidéo sur Futura]

[Nicolas666666]

tu veux minimiser la somme des carrés des distances

Méthode des moindres carrés?
Cela tombe bien, c'est celle que l'on me propose d'utiliser... Je vais m'y pencher un peu plus mais je ne vois pas trop le lien avec le barycentre? peux-tu me donner quelques indications?
Cordialement

[invite986312212]

eh bien tu n'as pas à rechercher itérativement le point qui minimise la somme des carrés des distances aux points du nuage, puisque la solution est déjà connue: c'est le barycentre. Ensuite pour déterminer le rayon, il faut bien utiliser un algorithme. Mais encore une fois, cette solution risque d'être assez éloignée de l'optimum. Imagine par exemple un nuage constitué de N+1 points, dont N sont très proches de 0, et le (N+1)ième à la distance d de 0. Si N est grand, le barycentre va se trouver près de 0 et le rayon va être proche de d, alors qu'un centre pris à la distance d/2 de 0 va conduire à un rayon proche de d/2.

[Nicolas666666]

la solution est déjà connue: c'est le barycentre

Ca ne me dit rien...
Donc en fait je ne trouve pas un résultat optimum.. J'imagine bien ton exemple, mais du coup je ne vois pas trop de solution pour trouver le meilleur cercle et je ne pense pas avoir le niveau pour comprendre et adapter ton algorithme..
Je ne vois donc pas trop comment me débrouiller dans un cas comme celui-ci..

[invite986312212]

salut,

j'ai pensé à l'algorithme suivant:

- on part de deux points: le plus petit cercle qui les contienne est celui qui a ces deux points pour diamètre.

- on a maintenant le plus petit cercle contenant N points et on doit ajouter un (N+1)ième point. S'il est déjà à l'intérieur du cercle, il n'y a rien à faire. Sinon, il faut modifier le cercle. On va chercher le centre du nouveau cercle sur le segment qui joint le centre de l'ancien cercle au nouveau point. Il faut faire ça itérativement, mais c'est relativement simple puisque c'est une optimisation sur une dimension.

-c'est fini quand on a épuisé le nuage (vraiment?)

par contre, je suis incapable de démontrer que cet algorithme conduit à la solution. A vue de pif, il doit donner un cercle pas trop mauvais.

[yat]

- on a maintenant le plus petit cercle contenant N points et on doit ajouter un (N+1)ième point. S'il est déjà à l'intérieur du cercle, il n'y a rien à faire. Sinon, il faut modifier le cercle. On va chercher le centre du nouveau cercle sur le segment qui joint le centre de l'ancien cercle au nouveau point. Il faut faire ça itérativement, mais c'est relativement simple puisque c'est une optimisation sur une dimension.

A mon avis non.

Exemple simple, on part de deux points A et B, le centre du cercle est au milieu I de [AB]. J'ajoute un point C tel que (AB) soit perpendiculaire à (AC). ABC est rectangle en A, le centre du cercle circonscrit est donc le milieu J de [AC], et il est évident que J n'est pas sur (IC).

[Jeanpaul]

Ca ne peut pas être le barycentre : si on a plein de points et qu'on en rajoute un très mal placé, le cercle va énormément changer alors que le barycentre variera peu à cause d'un effet de moyenne.
Intuitivement je dirais que le cercle solution a pour diamètre 2 des points ou bien il s'appuie sur 3 des points. Peut-on tâtonner et essayer toutes ces combinaisons 2 à 2 puis 3 à 3 ? Avec un ordinateur, c'est assez simple.

[invite986312212]

Intuitivement je dirais que le cercle solution a pour diamètre 2 des points ou bien il s'appuie sur 3 des points.

d'accord avec cette intuition. De plus, dans le premier cas, le diamètre est nécessairement constitué par les deux points les plus éloignés du nuage. Je continue à penser qu'on gagne à calculer d'abord l'enveloppe convexe du nuage. Les trois points (ou deux) appartenant au cercle circonscrit en font nécessairement partie.

[Nicolas666666]

Comment peut-on fixer parler de barycentre sachant que nous ne connaissons pas le centre?
Pour ma part j'ai pensé au fait que le cercle circonscrit le plus petit passe forcément par 3 points (ou deux?) donc si je trouve les 4 points les plus éloignés (celui ayant le plus petit x, le plus petit y, le plus grand x, le plus grand y) et en supprimant celui le plus proche des 3 autres, et que je fais le seul cercle passant par ces trois points, est-ce que je ne me rapproche pas de la solution?

Cordialement, merci de votre aide

[Nicolas666666]

En fait pour reprendre mon précédent message je ramènerai mon problème à trouver le cercle circonscrit à 4 points.. C'est déjà pas mal, mais ça reste compliqué et je ne suis pas sur que ce soit juste..
Cordialement

[yat]

Pour ma part j'ai pensé au fait que le cercle circonscrit le plus petit passe forcément par 3 points (ou deux?) donc si je trouve les 4 points les plus éloignés (celui ayant le plus petit x, le plus petit y, le plus grand x, le plus grand y) et en supprimant celui le plus proche des 3 autres, et que je fais le seul cercle passant par ces trois points, est-ce que je ne me rapproche pas de la solution?

En tout cas le cercle trouvé risque de ne pas contenir tous les points. En choisissant les x et y min et max, tu encadres tes points par un rectangle. Si les 4 points choisis sont éloignés des coins de ce rectangle, ça laisse de grandes zones couvertes par le rectangle mais pas par le cercle, et dans lesquelles on est susceptibles d'avoir des points.

[invite35452583]

Joli problème.
Premiers résultats :
soient trois points non alignés A, B et C le cercle de plus petit rayon contenant A, B et C est
i) le cercle circonscrit si le centre O est à l'intérieur de ABC
ii) le milieu du plus grand segment sinon
En effet, on cherche les minima de la fonction qui à un point M (suposé être le centre du cercle) associe max(AM,BM,CM) (le rayon minimal pour contenir les trois points).
Il y a au moins un minimum car si on place suffisamment loin cette fonction prend des valeurs trop grandes pour être minimales, on peut donc se ramener à un compact (cette fonction est continue).
Plaçons-nous en un point M autre que O, on peut supposer que celui-ci est tel que AM>BM et AM>=CM>=BM. On projette M sur (AC) en P, quand on déplace M vers P, la distance maximale entre AM, BM et CM restent AM si on se déplace que "très peu" car M->AM, M->BM, M->CM sont continues (si AM=CM on se déplace sur la médiatrice de [AC]). Or avec le choix effectué, AM diminue. Donc M n'est pas minimum.
D'autre part si M est sur un des côtés que l'on suppose (AC) (car si (AB)\{A} ou (CB)\{C} le déplacement précédent est toujours possible), on a AM>CM si M n'est pas au milieu de [AC]. Cette fois en se déplaçant vers A tout en gardant AM>BM, et AM>CM, on diminue la fonction égale localement à AM.
Il ne reste que les deux possibilités M au milieu d'un des côtés et M sur le centre O.
Si le centre du cercle circonscrit est à l'intérieur de ABC, ceci revient à dire que si on note J le milieu de [AC] alors BJ>AC/2, la fonction localement en I est égale à BM avec BM>AM et BM>CM, on peut diminuer la fonction en se déplaçant selon BM vers B. On peut faire de même avec les autres côtés et leurs milieux. Le seul minimum possible est O qui est minimum car celui-ci existe. (On vérifie aisémént que tout déplacement à partir de O dans cette configuration augmente strictement la fonction).
Si O n'est pas à l'extérieur, cela signifie que pour un (et un seul côté) le cercle ayant pour diamètre ce côté contient les trois points (ceci implique un angle en le troisème sommet>=pi/2 d'où l'unicité). Les deux autres milieux de côtés ne sont pas minimaux pour la même raison que ci-dessus. Il ne reste donc comme minimum possible que O et le milieu de ce côté or on a si on note R le rayon du cercle circonscrit R>=AC/2 (c'est toujours vrai) d'où, ici, R=max(AO,BO,CO)>=max(AJ,BJ,CJ) =AJ=CJ=AC/2. Le minimum est atteint au milieu (qui coïncide avec le O si B est sur le cercle de diamètre [AC]).
Dans tous les cas ce minimum est unique.

Maintenant cas général (méthode du gradient nettement simplifié ici)
On se place en un point M quelconque.
On considère le ou les points les plus éloignés de M. Ceux-ci peuvent être en nombre=1, 2 ou au moins 3. On va se ramener au cas 2 ou 3.
1er cas : A est un unique point du nuage qui maximise AiM
intuitivement : on "dépace" M vers jusqu'au moment où AM=BM pour au moins un autre point B.
"Constructivement" : on considère les médiatrices D(A,Ai) pour tous les points Ai du nuage autres que A, on regarde l'intersection I(A,Ai) de ces médiatrices avec [AM] (cette intersection est bien sur [AM] sinon en déplaçant (M') de M vers A on n'a jamais AiM'=AM' donc AM' reste strictement plus grand que AiM' même lorsque M' est en A contradiction).
Parmi ces points I(A,Ai) un (noté N=I(A,B) où b est le point du nuage correspondant) est le plus près de M, par construction on a AN=BN et >=AiN pour tous les autres points du nuage. On s'est donc ramené au 2ème cas (ou au 3ème si B n'est pas unique).
2ème cas : A et B sont deux points (et sont les seuls qui minimisent AiM)
on déplace N vers le milieu de [AB]
Deux possibilités :
1ère possibilité : l'intersecton des médiatrices de [AAi] et de la droite (IN) sont toutes à l'extérieur de [IN], alors en se déplaçant de N vers I on a toujours N'A=N'B>N'Ai pour tout Ai, et AN'=BN' diminue. Le point recherché est I, le rayon est AB/2. En effet, tout cercle contenant A et B autre que celui de diamètre [AB] (C(I,AB/2)) a un rayon >AB/2 donc un cercle contenant le nuage au un rayon non minimal car C(I,AB/2) est un cercle qui contient lui tous les points.
2ème possibilité : une médiatrice de [AAi] coupe [IN] (ailleurs qu'en N sinon on a une contradiction avec A et B sont les deux seuls poinst maximisant AiN). Soit C le point tel que cette intersection soit la plus proche de N, on note J cette intersction de la médiatrice et de [IN]. En J, par construction, AJ=BJ=CJ >=AiJ pour tout Ai. Par construction on a aussi I est du côté de la médiatrice de [AC] pour lequel les points L on a AL<CL, en particulier AI<CI et ABC est un triangle aigu (le centre du cercle circonscrit est à l'intérieur de ABC). Le cercle circonscrit à ABC contient tous les points du nuage et est déjà strictement minimum pour les trois seuls points A, B et C donc est minimum pour le nuage. Le cercle cherché est le cercle circonscrit à ABC.
3ème cas : A, B, C... sont des points maximisant AiM
Tous ces points sont un même cercle de centre O.
Deux possibilités :
1ère possibilité : ils ne sont pas tous dans un même demi-plan dont la frontière passe par O (O donc à l'intérieur d'au moins un des triangles, on en prend deux A et B non alignés ensemble avec O, existe car sont plus de trois, on considère l'intersection des demi-plans bordés un par (AO) l'autre par (BO) ne contenant pas le deuxième point, cette intersction contient un point sinon il y a un des demi-plans qui est vide contradiction). On a alors le cercle minimal est le cercle circonscrit à ces points (cf. fin du 2ème cas pour l'argument).
2ème possibilité : ils sont tous dans un même demi-plan. Il y a donc deux points extrémaux A et B (ceux pour lesquels tous les autres sont dans l'arc aigu formé par ces deux points). En se raprochant du milieu I de [AB] on diminue aussi la distance à ces points (qui devient strictement plus petite que la distance à A et à B), on se ramène donc au 2ème cas (pour lequel on a conclu pour les deux possibilités).

Cette méthode ramène l'algorithme à de l'ordre de n au lieu (de n² et) n³ pour la méthode consistant à regarder tous les couples et triplets de points.

[Nicolas666666]

Merci d'avoir pris le temps de répondre à mon problème!
Je n'ai pas trop le temps de m'y pencher ce soir mais encore merci!

[Nicolas666666]

Bonjour! Encore merci pour ta réponse très compléte! Cependant je n'ai pas tout compris..

"Constructivement" : on considère les médiatrices D(A,Ai) pour tous les points Ai du nuage autres que A, on regarde l'intersection I(A,Ai) de ces médiatrices avec [AM] (cette intersection est bien sur [AM] sinon en déplaçant (M') de M vers A on n'a jamais AiM'=AM' donc AM' reste strictement plus grand que AiM' même lorsque M' est en A contradiction).

Je ne comprends pas trop ici, pourrias-tu essayer de m'expliquer un peu plus?

l'intersecton des médiatrices de [AAi] et de la droite (IN) sont toutes à l'extérieur de [IN], alors en se déplaçant de N vers I on a toujours N'A=N'B>N'Ai pour tout Ai, et AN'=BN' diminue.

De même je ne comprends pas..

2ème possibilité : une médiatrice de [AAi] coupe [IN] (ailleurs qu'en N sinon on a une contradiction avec A et B sont les deux seuls poinst maximisant AiN). Soit C le point tel que cette intersection soit la plus proche de N, on note J cette intersction de la médiatrice et de [IN]. En J, par construction, AJ=BJ=CJ >=AiJ pour tout Ai. Par construction on a aussi I est du côté de la médiatrice de [AC] pour lequel les points L on a AL<CL, en particulier AI<CI et ABC est un triangle aigu (le centre du cercle circonscrit est à l'intérieur de ABC). Le cercle circonscrit à ABC contient tous les points du nuage et est déjà strictement minimum pour les trois seuls points A, B et C donc est minimum pour le nuage. Le cercle cherché est le cercle circonscrit à ABC.
3ème cas : A, B, C... sont des points maximisant AiM
Tous ces points sont un même cercle de centre O.
Deux possibilités :
1ère possibilité : ils ne sont pas tous dans un même demi-plan dont la frontière passe par O (O donc à l'intérieur d'au moins un des triangles, on en prend deux A et B non alignés ensemble avec O, existe car sont plus de trois, on considère l'intersection des demi-plans bordés un par (AO) l'autre par (BO) ne contenant pas le deuxième point, cette intersction contient un point sinon il y a un des demi-plans qui est vide contradiction). On a alors le cercle minimal est le cercle circonscrit à ces points (cf. fin du 2ème cas pour l'argument).
2ème possibilité : ils sont tous dans un même demi-plan. Il y a donc deux points extrémaux A et B (ceux pour lesquels tous les autres sont dans l'arc aigu formé par ces deux points). En se raprochant du milieu I de [AB] on diminue aussi la distance à ces points (qui devient strictement plus petite que la distance à A et à B), on se ramène donc au 2ème cas (pour lequel on a conclu pour les deux possibilités).

Là non plus mais je t'avouerai que je n'ai pas pris le temps; je m'y pencherai plus demain..
Cordialement, et encore merci beaucoup!

[Nicolas666666]

Je viens de m'y repencher un peu plus, et sans me préoccuper des cas particuliers et sans calculs et si j'ai bien compris :
Je prends un point M au hasard, et je me déplace sur la droite qui le relie au point le plus éloigné, noté A. (MA étant le rayon)
Forcément si je trouve un point B "sortant" de ce rayon je m'arrête d'aller vers A car B ne serait plus dans le rayon.
Et là j'avance vers le milieu de AB, noté I pour me rapprocher du diamètre AB si cela est possible. Si je rencontre un point C sortant de ce diamètre je dois m'arrêter car il sortirait alors du cercle de rayon MA=MB.
Sans avoir trop compris la suite de ce que tu as dit (desolé je m'y perds un peu) j'imagine que le cercle circonscrit le plus petit va forcement passer par A,B et C..
Pourrais-tu me dire si je ne me trompe pas?
Il va falloir passer sous excel...
Encore merci de ton aide!

[invite35452583]

Je viens de m'y repencher un peu plus, et sans me préoccuper des cas particuliers et sans calculs et si j'ai bien compris :
Je prends un point M au hasard, et je me déplace sur la droite qui le relie au point le plus éloigné, noté A. (MA étant le rayon)
Forcément si je trouve un point B "sortant" de ce rayon je m'arrête d'aller vers A car B ne serait plus dans le rayon.
Et là j'avance vers le milieu de AB, noté I pour me rapprocher du diamètre AB si cela est possible. Si je rencontre un point C sortant de ce diamètre je dois m'arrêter car il sortirait alors du cercle de rayon MA=MB.
Sans avoir trop compris la suite de ce que tu as dit (desolé je m'y perds un peu) j'imagine que le cercle circonscrit le plus petit va forcement passer par A,B et C..
Pourrais-tu me dire si je ne me trompe pas?

C'est à peu près cela sauf lorsque l'on tombe sur C (plus éventuellement d'autres points sur le cercle circonscrit à ABC), c'est moi qui me suis trompé dans le 1er post.
2 possibilités à partir de là :
1) Tous les points sur le cercle ABC (càd les points les plus éloignés du centre du cercle) sont sur un même demi-cercle alors il existe des points D et E "extrémaux" (tous les points sont de l'autre côté de (DE) par rapport à O). Alors, on voit plus ou moins facilement que la pente descendante la plus importante est vers le milieu de [DE], dans cette diretion localement on a r(M)=max(DM,EM) (on est de fait revenu à une situation où il n'y a que deux points qui sont le plus éloignés et on recommence à partir de là).
2) trois points du cercle forment un triangle aigu ou rectangle et alors on est au minimum (car est minimm pour ce triangle)
A remarquer on peut se demander si ces passages 2 points(déplacement le long d'une médiatrice)->trois points ou plus (changement de direction)->2 points... (avec possibilité d'arrêt au milieu de deux points ou au centre de trois points formant un triangle aigu à chaque fois) est sont nombreux. Il ne peut y avoir plus de changement de direction qu'il n'y a de points, en effet :
si le centre de ABC est un lieu de changement de direction (on supposera que A et B jouent le rôle de D et E d'avant), les prochains centres sont tous dans l'intérieur de l'intersection des ce'rcles de centre A et B et passant par O (car la distance maximale est strictement décroissante), or cette zone a une intersection vide avec la zone des points plus distants de C par rapport à A et B , C ne sera plus jamais dans ce processus (s'il l'a djà été) un des points les plus éloignés.
Cette méthode est de l'ordre de nN donc (n étant le nombre de points du nuage et N le nombre de points de l'enveloppe convexe, qui n'a pas besoin d'être déterminé mais les points les plus éloignés sont sommets de la frontière l'enveloppe connexe)

Il va falloir passer sous excel...

Ce n'est pas une petite difficulté vu le processus défini ci-dessus.

[Nicolas666666]

Mince... La dernière décomposition en deux cas me pose problème.. Et en ayant fait abstraction j'arrive à quelque chose de pas si mal sur un exemple de courbe quelconque..
Mais ce fut laborieux car je ne sais pas encore utiliser les macros... Bref je vais voir si j'ai réellement un problème si je saute la dernière étape...
(A ce propose si quelqu'un trouve un contre-exemple en sautant la dernière étape, je suis preneur!)
Cordialement!

[Nicolas666666]

Pour revenir sur le dernier problème survenu, n'y aurait-il pas un endroit ou je serais sur que le point M choisi (plus au hasard en fait) ne me ramènerait pas à A B C sur le même demi-cercle?
(par exemple à l'intérieur du rectangle circonscrit aux points, ou encore au centre du cercle des moindres carrées...)
Cordialement!

[Nicolas666666]

Bonjour à tous, voilà après avoir revu notre cahier des charges du projet, j'en reviens à trouver le cercle des moindres carrés.. Et j'avoue être un peu perdu: je pose mes équations du types :
et après je dois mettre sous forme matricielle... mais là je bloque car forcément en dévelopant je trouve des et des , de même pour les ..
Pourriez-vous me mettre sur la voie?
Cordialement!

[Nicolas666666]

1) Tous les points sur le cercle ABC (càd les points les plus éloignés du centre du cercle) sont sur un même demi-cercle alors il existe des points D et E "extrémaux" (tous les points sont de l'autre côté de (DE) par rapport à O). Alors, on voit plus ou moins facilement que la pente descendante la plus importante est vers le milieu de [DE], dans cette diretion localement on a r(M)=max(DM,EM) (on est de fait revenu à une situation où il n'y a que deux points qui sont le plus éloignés et on recommence à partir de là).

Pourrais-tu essayer d'expliciter ce problème s'il te plait?
Je m'y perds un peu...
Cordialement!

[invite35452583]

Pourrais-tu essayer d'expliciter ce problème s'il te plait?
Je m'y perds un peu...
Cordialement!

On a un certain nombre n de points du nuage à une distance R d'un point O, les autres points du nuage étant à l'intérieur de ce cercle.
Sur un cercle si on choisit un sens pour tourner et si on a seulement un nombre fini de points il y a une notion de successeur : A(i+1) est le successeur de A(i) si en tournant dans le sens indiqué il n'y a aucun point du nuage entre A(i) et A(i+1).
Soit a l'angle au centre maximal entre deux points consécutifs, on note A et B ces points. On a ceci :
i) Si a<pi, trois de ces points (au moins) forment un triangle aigu, en effet soient A' et B' les points diamétralement opposés à A et B alors comme l'angle au centre entre B' et A' est égal à celui entre A et B par maximalité de A il y a au moins un point C du nuage entre B' et A'. L'angle entre A et C est inférieur à celui entre A et A' donc inférieur à pi, idem entre C et B. Le triangle ABC est donc aigu.
ii) Si a=pi, il existe au moins un triangle rectangle
Dans les cas i) et ii) M est le centre du cercle recherché (vu).
iii) Si a>pi, alors tous les points sont d'un même côté par rapport à la demi-droite d parallèle à (AB) passant par O.
Tous les triangles formés par A, B et un troisième point C du nuage sont obtus en C. Les points du plan pour lesquels C est le point parmi les trois qui est le plus distant est un secteur angulaire bordé par la médiatrice de A et C et celle de B et C situé entièrement dans le demi-plan bordé par d (pas très dur à montrer et sur une figure c'est évident).
Maintenant, les points M tels que MA<=OA et MB<=OB sont les points de l'intersection du disque de centre A et de rayon OA et du disque de centre B et de rayon OB=OA. Ces points sont tous du même côté par rapport à d. Pour les points en dehors de cette zone r(M)>=max(AM,BM)>AO=BO=r(O) au moins un des deux entre Am et BM est plus grand, ces points ne nous intéressent donc pas. Cette zone où en se déplaçant r(M) décroît est donc telle que max(Am,Bm,AiM)=max(AM,BM) les Ai étant les points sur le cercle ( au quel on peut ajouter tous ceux qui sont la partie du disque de l'autre côté que O par rapport à AB). Localement ce sont les seuls points du nuage intéressants en effet, les autres vérifient A'iM>AM. Donc on minimise r(M) en suivant à partir de O la médiatrice de A et de B ou autrement dit en allant vers le milieu de A et de B jusqu'à une prochaine intersection avec une médiatrice de A et d'au moins un autre point C, qui sera aussi sur la médiatrice de B et de ces points C, ou jusqu'au milieu de A et de B.
Les points O intersection de plusieurs médiatrices sont donc soit des fins de parcours soit des changements de direction (il est facile de voir qu'il est contradictoire avec ce qui vient d'être vu de supposer que M arrive en O par la médiatrice de A et de B : si A et B sont vraiment maximaux alors localement on est du côté où AM<AO !)

Maintenant pour la programmation : la notion de points successeurs est évidente visuellement mais pour programmer on peut simplifier.
On considère les points suivants : A1 et A2 d'abcisses respectivement maximale et minimale pour les points d'ordonnée>=ordonnée du centre
B1 et B2 les points d'abcisses respectivement maximale et minimale pour les points d'ordonnée<=ordonnée du centre
Si A1 et A2 n'existent pas ou si B1 et B2 n'existent pas alors on est dans le cas iii) (tous les points sont sur un même dmi-cercle dans le sens strict)
Sinon on a toujours angle entre A1 et A2 et angle au centre entre B2 et B1 <=pi.
Il reste à comparer pi à l'angle entre A2 et B2 et celui entre B1 et A1 (or pour cela il suffit de conidérer l'abcisse de B2 et l'opposé de A2/O et l'abcisse de B1 par rapport à l'opposé de A1).
Si un de ses angles est>pi ils sont tous dans un même demi-cercle (par définition de ces points). Et on a les deux points successifs formant un angle>pi.
Si aucun n'est inférieur à pi alors le maximum est <=pi (rien n'assure que l'on a trouvé les points d'angle maximal, ceux-ci peuvent se trouver entre A1 et A2 par exemple, mais ça n'a pas d'importance on a bien max<=pi) et alors on est dans la situation i) ou ii).
Cette dernière méthode est plus facile à programmer.

Il reste néanmoins qu'avec Excell, c'est toujours aussi horrible. C'est une contrainte imposée par quoi ?
Sinon il reste la voie de l'exhaustivité* (définir les paires n'est pas très dur par contre les triplets ??) (j'appelle l'exhaustivité : on regarde ltous les milieux de segment, tous les milieux des triangles et on regarde la distance maximale aux points du nuage pour chacun de ses points, puis on prend le minimum)

Sinon, c'est quoi cette histoire de cercle des moindres carrés ? un autre problème car il est impossible que les deux cercles coïncident. En gros le cercle minimal circonscrit ne dépend que d'un petit nombre de ces points tandis que celui des moindres carrés dépend de tous les points : imagine un nombre grand N de points très proches et un autre plus distant (les distances entre les premiers points sont négligeables ainsi que la différence des longueurs entre ce dernier point et un de ces premiers par rapport à n'importe lequel). Le milieu du cercle circonscrit minimal sera aux environs du milieu d'un des premiers points et du dernier, tandis que celui des moindres carrés sera proche (et d'autant plus proche que N est grand) des premiers points. De même pour une configuration où les deux centre coïncident, il suffit d'ajouter un point dans le cercle circonscrit autre qu'au centre pour que les deux ne coïncident plus : celui des moindres carrés sera modifié mais celui du cecle circonscrit minimal).

[Nicolas666666]

Bonjour!
Voilà j'ai testé d'autres méthodes à mon avis plus faciles à programmer et après quelques recherches j'en suis arrivé à utiliser la méthode du recuit simulé.
Mais là je bloque car je ne sais pas quel doit être mon test de probabilité pour éviter de tomber dans un minimun local...
Cordialement!

[invite35c04340]

Salut. Apparemment ce probleme est connu, sur google tu trouveras des trucs en cherchant "minimal enclosing circle" ou "smallest enclosing circle".

[Nicolas666666]

En effet beaucoup plus rentable qu'une recherche en français!
Par contre sur ce site j'ai un petit problème de traduction pour le point 4 :

http://www.personal.kent.edu/~rmuham.../centercli.htm

At this stage, we a circle, C, that passes through two or more points of a given set. If the circle contains an interval (point-free interval) of arc greater than half the circle's circumference on which no points lie, the circle can be made smaller. Let D and E be the points at the ends of this point-free interval. While keeping D and E on the circle's boundary, reduce the diameter of the circle until we have either case (a) or case (b).

Quelqu'un pourrait me donner un coup de main pour ce paragraphe?
Cordialement!

[invite35c04340]

At this stage, we a circle, C, that passes through two or more points of a given set. If the circle contains an interval (point-free interval) of arc greater than half the circle's circumference on which no points lie, the circle can be made smaller. Let D and E be the points at the ends of this point-free interval. While keeping D and E on the circle's boundary, reduce the diameter of the circle until we have either case (a) or case (b).

"A cette étape, nous [avons] un cercle, C, qui passe par au moins 2 points d'un ensemble donné. Si le cercle contient un intervalle d'arc, plus grand que la moitié de la circonférence, et sur lequel il n'y a aucun point, le cercle peut être rendu plus petit. Soient D et E les points aux extrémités de cet intervalle sans point. En gardant D et E dans la frontière du cercle [i.e sur le cercle je suppose], réduisez le diamètre du cercle jusqu'à ce que l'on soit dans l'un des cas (a) ou (b)"