Discussion :

[[Hugo]]

Bonjour,

Je suis à la recherche d'un algo qui détermine le plus petit cercle circonscrità un convexe... est-ce que quelqu'un aurait des pistes sur le sujet ?

Merci

Hugo

[Emmanuel Deloget]

Bonjour,

Je suis à la recherche d'un algo qui détermine le plus petit cercle circonscrit à un convexe... est-ce que quelqu'un aurait des pistes sur le sujet ?

Merci

Hugo

A un quoi convexe ? Tous les polygones convexes ne sont pas inscriptibles - il faut des conditions bien particulières.

1) tous les triangles (le centre du cercle est à l'intersection des médianes des cotés du triangle).
2) tous les rectangles (dans ce cas le centre du cercle circonscrit est aussi le barycentre du polygone)
3) tous les polygones à N cotés égaux (dans ce cas le centre du cercle circonscrit est aussi le barycentre du polygone).
4) tous les polygones dont les médianes aux cotés sont concourantes (c'est à dire qu'elle se croisent au même point).

De plus, la définition mathématique d'un cercle circonscrit à un polygone implique que ce cercle est unique puisqu'il passe par tous les sommets du polygone. Il est donc de fait le plus petit.

Bref, tout ça pour dire que je ne suis pas tout à fait sûr que la question soit la bonne...

[[Hugo]]

La question est bonne, j'en suis sûr , mais peut-être mal posée...
Je précise: j'ai un ensemble de points qui forment un convexe quelconque - on sait juste que c'est un convexe - comment déterminer le plus petit cercle par lequel ce convexe est "circonscrit" ? Donc pas au sens "tous les points du convexe sur le cercle" mais "tous dedans, au plus près".
Merci de ta réponse/suggestion !!

[Emmanuel Deloget]

La question est bonne, j'en suis sûr , mais peut-être mal posée...
Je précise: j'ai un ensemble de points qui forment un convexe quelconque - on sait juste que c'est un convexe - comment déterminer le plus petit cercle par lequel ce convexe est "circonscrit" ? Donc pas au sens "tous les points du convexe sur le cercle" mais "tous dedans, au plus près".
Merci de ta réponse/suggestion !!

Pas sûr que ça aide vraiment:
1) rechercher le point d'intersection des médianes. Si toutes les médianes son concourantes en C, alors il existe un cercle circonscrit dont le centre est C et dont le rayon est CS (ou S est un des sommet du polygone).

2) dans le cas contraire, aucune idée (si ce n'est peut être que les points d'intersection des médianes doivent former un autre polygone, dont l'isobarycentre peut être un candidat au titre de centre du plus petit cercle contenant tous les points du polygone; mais point de preuve mathématique == point de réponse valide).

[screetch]

Un tel cercle passe au moins par 3 points du polygone. en effet si un cercle passe par seulement 2 points alors tu peux le retrecir jusqu'a trouver un troisieme point.

j'ai bien une methode peu performante...
chercher tous les triangles du polygones
(si les points du polygones sont A,B,C,D,E dans cet ordre alors je pense qu'en ayant (A,B,C),(A,B,D),(A,B,E),(B,C,D),(B,C,E)...). prendre tous leurs cercles circonscrits. si tous les points du polygone sont dedans, alors on le garde, sinon on le rejette. a la fin on garde le plus petit.

[bafman]

en fait, je pense su'il y a un probleme de sens dans le terme circonscrit.
si on prend ceci, effectivement, on peut ne pas avoir de cercle circonscrit (par exemple avec un losange, qui est bien convexe mais n'a pas de cercle circonscrit).
par contre, si, comme je le suppose, tu veut parler du plus petit cercle contenant le polygone, alors il suffit de trouver les deux extrémité les plus éloignées, et tu a trouvé le diamètre de ton cercle