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

[[Hugo]]

Merci à tous pour vos suggestions

J'avais pensé au coup de parcourir les triplés de points, mais il me semble que ça va coûter cher en temps de calcul, si N augmente (O(N3) ?)...
Je vais tenter l'idée de Bafman - qui risque elle aussi de coûter un peu cher (O(N2) ?), non ? Elle me paraît conceptuellement trop simple, mais je ne parviens pas à trouver de contre exemple en trente secondes... on va tester pour voir .
Je me demandais s'il n'existe pas des solutions plus optimisées ?
Si qqn a des lumières, je suis toujours preneur !
Encore merci à tous !
Hugo

[screetch]

oui effectivement bafman a raison =) je viens de trouver mon contre exemple pour que le faire passer par un troisieme point fasse "grandir" le cercle et non pas diminuer.

=> trouver les deux points les plus eloignés

[[Hugo]]

screetch : c'est quoi ton contre exemple ?

[screetch]

un losange =)

[[Hugo]]

Ca y est, j'ai mis le doigt sur l'os : la solution de bafman ne fonctionne pas ... le problème est non trivial. Rien qu'avec trois points ça se voit :si on trace un cercle avec comme diamètre deux points opposés - belle tautologie - on peut en placer un à l'extérieur du cercle dont la distance à chacun des points choisis pour le diamètre sera inférieur au diamètre...
Je cherche toujours, du coup...
Merci encore !
Hugo

[[Hugo]]

screech : de fait... ça ne marche pas ! merci de ta réponse

[Alp]

Tu risques d'avoir plus de réponses dans le forum Algo

[[Hugo]]

Ah ? Pas vu ce forum ! Je vais poster là-bas ! Merci du conseil

Hugo

[Emmanuel Deloget]

un losange =)

Ou un triangle avec un angle ouvert.

Rien qu'avec trois points ça se voit :si on trace un cercle avec comme diamètre deux points opposés - belle tautologie - on peut en placer un à l'extérieur du cercle dont la distance à chacun des points choisis pour le diamètre sera inférieur au diamètre...

cf. un triangle isocèle.

Je doute qu'il soit possible de déterminer le plus petit cercle sans passer par un algorithme qui teste les positions de tous les centres possibles. Mon idée sur l'isobarycentre des intersections des médianes n'est pas spécialement intelligente (puisque je peux construire des polygones convexe tels que les intersections des médianes forment un polygone non convexe qui est plus grand que mon polygone originel; pas très utile tout ça).

[Prof_math_Creajeux]

Voici l'algo que je te propose :

tu prends les valeurs min et max en x et en y : cela revient à calculer la longueur des segments projetés par ton polygone sur chacun des axes de coordonnées.
Tu calcules le milieu de ces deux segments projetés => ça te donne le centre de ton cercle.
Tu calcules la plus grande distance entre ce centre et tes sommets de poly => ça te définit le rayon le plus grand passant encore par un de tes sommets.

Cette procédure te grarantit que le polygone est entièrement contenu dans le cercle.

J'ai essayé pour divers polygones, ça a l'air de bien fonctionner.
Je te donnes le code suivant en Scilab (logiciel libre pour les maths) si tu ne l'as pas, considère ceci comme du pseudo-code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
L=list([5 0], [7 1],[6 5],[4 5],[2 1.5], [5 0]) ; // Définition des sommets du poly
 
point_x = [];
point_y = [];
 
min_x = 1000; //mettre n'importe quelle grande valeur que tu n'utilises pas
max_x = 0;
 
min_y = 1000; //mettre n'importe quelle grande valeur que tu n'utilises pas
max_y = 0;
 
for point=L, //Recherche des maxi et mini
 
  point_x = [point_x point(1)];
  point_y = [point_y point(2)];
   if point(1)>max_x then
   max_x = point(1);
   elseif point(1)<min_x then
   min_x = point(1);
   end
 
   if point(2) > max_y then
   max_y = point(2);
   elseif point(2) < min_y then
   min_y = point(2);
   end
 
end
plot2d(point_x, point_y, 1, rect=[-2,-2,9,9]); // dessin polygone
 
centre = [(max_x+min_x)/2 (max_y+min_y)/2];
 
rayon = 0;
for point=L, //recherche distce centre-sommet maxi pour définir rayon
 
  dist = norm(point-centre);
  if dist>rayon then
  rayon = dist;
  end
 
end 
 
 
//Tracé du cercle : Scilab n'a pas de circle - Ceci est inutile dans la plupart des autres langages
x=-rayon+centre(1):0.1:centre(1)+rayon+0.1; 
y = centre(2) + sqrt(rayon^2 - (x-centre(1)).^2);
y2 = centre(2) - sqrt(rayon^2 - (x-centre(1)).^2);
 
plot2d(x, y, 1, rect=[-2,-2,9,9]);
plot2d(x, y2, 1, rect=[-2,-2,9,9]);

En espérant que ça puisse t'aider.
L'avantage : ça marche aussi pour les poly concaves.

John

[[Hugo]]

Merci beaucoup pour cette suggestion .
Je vais implémenter tout ça - je suis plus C++ que scilab . Mais je n'ai pas encore implémenté Welzl... Ca marcherait en dimension supérieure à 2 ? (dans mon cas, on peut avoir besoin de ce genre d'algo en 5 ou 2D...)
Encore un grand merci !!

Hugo