Répondre à la discussion
Affichage des résultats 1 à 28 sur 28

Cercle circonscrit à un nuage de plan



  1. #1
    Nicolas666666

    Cercle circonscrit à un nuage de plan


    ------

    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!

    -----

  2. Publicité
  3. #2
    invite986312212
    Invité

    Re : Cercle circonscrit à un nuage de plan

    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.

  4. #3
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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

  5. #4
    invite986312212
    Invité

    Re : Cercle circonscrit à un nuage de plan

    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.

  6. A voir en vidéo sur Futura
  7. #5
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par ambrosio Voir le message
    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

  8. #6
    invite986312212
    Invité

    Re : Cercle circonscrit à un nuage de plan

    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.

  9. Publicité
  10. #7
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par ambrosio Voir le message
    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..

  11. #8
    invite986312212
    Invité

    Re : Cercle circonscrit à un nuage de plan

    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.

  12. #9
    yat

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par ambrosio Voir le message
    - 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).

  13. #10
    Jeanpaul

    Re : Cercle circonscrit à un nuage de plan

    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.

  14. #11
    invite986312212
    Invité

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par Jeanpaul Voir le message
    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.

  15. #12
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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

  16. Publicité
  17. #13
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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

  18. #14
    yat

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par Nicolas666666 Voir le message
    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.

  19. #15
    homotopie

    Re : Cercle circonscrit à un nuage de plan

    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) n3 pour la méthode consistant à regarder tous les couples et triplets de points.

  20. #16
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  21. #17
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

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

    Citation Envoyé par homotopie Voir le message
    "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?

    Citation Envoyé par homotopie Voir le message
    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..

    Citation Envoyé par homotopie Voir le message
    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!

  22. #18
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  23. Publicité
  24. #19
    homotopie

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par Nicolas666666 Voir le message
    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)

    Citation Envoyé par Nicolas666666 Voir le message
    Il va falloir passer sous excel...
    Ce n'est pas une petite difficulté vu le processus défini ci-dessus.

  25. #20
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  26. #21
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  27. #22
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  28. #23
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par homotopie Voir le message
    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!

  29. #24
    homotopie

    Re : Cercle circonscrit à un nuage de plan

    Citation Envoyé par Nicolas666666 Voir le message
    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).

  30. Publicité
  31. #25
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  32. #26
    bernardosoares3

    Re : Cercle circonscrit à un nuage de plan

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

  33. #27
    Nicolas666666

    Re : Cercle circonscrit à un nuage de plan

    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!

  34. #28
    bernardosoares3

    Re : Cercle circonscrit à un nuage de plan

    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)"
    Dernière modification par bernardosoares3 ; 23/12/2007 à 23h24.

Discussions similaires

  1. Plan moyen d'un nuage de points
    Par mécano41 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 11/11/2007, 14h20
  2. coordonnees de centre de cercle circonscrit
    Par robreda dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 15/03/2007, 17h44
  3. Déterminer le centre d'un cercle par l'équation du cercle et un point
    Par neo75013 dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 09/03/2007, 20h30
  4. les points du cercle circonscrit
    Par scholasticus dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 28/02/2007, 12h37
  5. coordonnes du centre du cercle circonscrit
    Par arnaud91 dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 15/04/2006, 10h51