ptit prob de géométrie

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





Posted by: Spaz

Bonjour à tous,

J'ai un petit prob de géométrie que mes biens piêtres capacitées en math ne savent pas résoudre

Soit un cercle de rayon r1.
Je cherche, pour commencer, à placer n cercles identiques à l'intérieur de celui-ci. n > 1, et ces cercles ne peuvent s'entrecouper.
Comment calculer le rayon r2 maximum de ces cercles ? et les coordonnées du centre de ceux-ci ?

Egalement, un peu à part, si je connais le rayon de n cercles, comment puis-je savoir si ceux ci rentre dans mon cercle C1 ? Y a-t-il une formule, un algo qui pourrait m'aider à trouver la meilleur répartition possible ?

Merci par avance


Posted by: Spaz

Après 3 dessins, je pense avoir trouver.

R2 = R1 / (1+1/sin(pi/n))

Si qq pouvait me le confirmer


Posted by: scelerat

Citation:
Posté par Spaz
Après 3 dessins, je pense avoir trouver.

R2 = R1 / (1+1/sin(pi/n))

Si qq pouvait me le confirmer

Ca ne me parait que le debut.
Certes, si on regarde quel rayon pour mettre m petits cercles a touche touche contre la face interne du grand cercle, on a bien : R2 / (R1-R2) = sin (pi/m). Mais il nous reste au centre un espace vide circonscrit au cercle de rayon R1 - 2R2, dans lequel on peut parfois mettre un certain nombre de cercles. Et le plus complique, c'est que cet espace est un tout petit peu plus accommodant que le cercle de rayon R1-2R2....


Posted by: Spaz

Oui, je venais de remarquer. Mais je peux le résoudre récursivement, ce qui est parfait pour moi.
J'avais donc trouver juste, merci de la confirmation

D'ailleurs, un rapide calcul m'a amené à ce que, pour que le cercle circonscrit à l'intérieur soit assez grand, il faut n >= 10. Mais je suis pas sur du tout sur ca :)


Posted by: scelerat

Citation:
Posté par Spaz
D'ailleurs, un rapide calcul m'a amené à ce que, pour que le cercle circonscrit à l'intérieur soit assez grand, il faut n >= 10. Mais je suis pas sur du tout sur ca :)


Je dirais 7. Prenons un nid d'abeilles : 1 hexagone entoure de 6 autres, je mets un cercle dans chaque hexagone...


Posted by: Spaz

Effectivement, j'avais posé que l'on cherchait 2R2 <= R1/2, alors qu'on cherche 3R2 <= R1, ce qui nous amène au final à sin pi/n <= 1/2, et sin pi/6 = 1/2 :)
Ce qui nous donne bien 6 cercles "extérieurs", et 1 intérieur, donc 7
Merci scelerat


Posted by: Patastronch

Et en quoi vous prouvez que c'est optimal ?
Sans vouloir trop m'avancer ca pue le probleme NP-Complet.


Posted by: scelerat

Citation:
Posté par Patastronch
Et en quoi vous prouvez que c'est optimal ?
Sans vouloir trop m'avancer ca pue le probleme NP-Complet.

Ai-je dit que c'etait optimal ?...
Par contre, ca ne me parait pas facile a prouver, mais je suis persuade que pour n=1, n=7,n=19, etc. la disposition en nid d'abeilles est optimale, et meme peut-etre aussi pour n=3, n=13, n=31, etc.
Et etant donnee une disposition optimale de n cercles de rayon R2, pour en ajouter un n+1 ieme, on doit pouvoir definir comment choisir le trou a agrandir pour l'y mettre (le plus a la peripherie possible, et initialement le plus grand, il y a un compromis sur ces deux aspects) de maniere a ce que l'augmentation de R1 soit minimale.










-