Nombre de cercles dans un carré

[Ben314]

Moi je pige pas. Tous les sacs d'un même container ont le même rayon ? Si oui alors y'a rien de compliqué, tu peux trouver une formule mathématique.

Tu es sûr que, même dans le cas où tout les cercles sont de même rayon, on a pas des problèmes "d'effet de bord" ?
(c'est une vrai question à laquelle... je n'ai pas la réponse...)

[Cliffe]

Si on suppose que la manière optimale de ranger est celle de chan alors il suffit de calculer la hauteur de 3 cercles empilés pour obtenir le nombre de lignes que l'on peut construire :

[CENTER] [/CENTER]

[fatal_error]

Hello,

alors déjà, je crois que ya rien de démontré.
Pour démontrer qu'une solution est optimale, il faut chercher toutes les config possibles ...

Le sujet se réfère aux mots clés circle packing (généralement into square, mais ca doit pouvoir aussi s'appliquer aux rectangles)

Pour ce qui est de ton cas,
h = Longueur
w = largeur
tu cherches r pour maximiser l'espaces occupé.

Mais si tu te bases sur le benpacking, tu vois que sur les bords t'as des demi-cercles (espace perdu).
Mais du coup, si tu prends des cercles 6 fois plus petits (pour mettre pleins d'hexagones dans l'hexagone...), ben tu vas garder la proportion de surface couverte, et tu pourras en enquiller un peu plus sur les bords. Donc il faudrait définir c'est quoi la taille mini...

Sinon toujours en partant du benpacking,
on a envie de poser x le nombre entier max de cercles sur une ligne (largeur), y sur une colonne (longueur)
et d'avoir
x*d = w
y*d = h
d'ou x/y = w/h <=> yw = hx
ce qui se résoud assez facilement avec le ppcm(w,h) je pense

[Ben314]

x*d = w
y*d = h
d'ou x/y = w/h yw = hx

Il me semble que c'est plus compliqué que ça.
Regarde le dessin proposé par Chan 3 post plus haut (Aujourd'hui 11h10) : autant il y a bien des notions de "lignes", mais pas vraiment de notion de "colonnes".
Perso, là où je ne sais pas trop ce que ça donne, c'est qu'il a mis 11 cercles sur la ligne du bas tassés les uns contre les autres à gauche donc avec pas mal de "rab" à droite, ce qui lui a permis d'en remettre 11 à la ligne au dessus.
Mais si le "rab" de droite avait été trop petit, il risquait d'être limité à 10 cercles pour la 2em ligne et dans ce cas, il était clair qu'il valait mieux espacer régulièrement les cercles de la ligne du bas pour que la 2em ligne soit légèrement plus basse (avec l'espoir qu'à la fin, ça permettait de mettre une ligne de plus...)

Perso, je commencerais bien par regardera ce que ça donne comme algo. en étudiant juste 2 types de remplissages : soit avec le même nombre par lignes comme sur le dessin de chan (en espaçant les cercles s'il y a du "rab" sur la 2em ligne), soit en alternant une ligne à n puis une à n-1 (toujours en écartant pour rapprocher les lignes)

[Cliffe]

tu cherches r pour maximiser l'espaces occupé.

Dans ce cas tu prend 'r' infiniment petit.

[Quenton999]

Bonjour,

Merci à tous pour vos réponses, c'est formidable de pouvoir trouver de l'aide comme ça sur internet ! Afin de mieux illustrer le problème auquel je fais face, voici une illustration :



Il semble évident que la solution de gauche permettra de mettre plus de sacs dans le conteneur que celle de droite. Néanmoins, je n'arrive pas à formuler cette problématique sur tableur.

Je crois que Ben est mieux parvenu à formuler la difficulté que moi ^^

Merci encore !

[fatal_error]

Regarde le dessin proposé par Chan 3 post plus haut (Aujourd'hui 11h10) : autant il y a bien des notions de "lignes", mais pas vraiment de notion de "colonnes".

ui je les ai parqués en square ... :hum:


Il y a également cet agencement
http://www.sciencedirect.com/science/article/pii/S0305054812001141
(mais pas moyen que je paye pour ca!!)

Je crois que leur idée, c'est d'essayer r fixé, rectangle fixé, avec n=1, puis n=2...jusqu'à ce qu'on puisse plus fitter de cercles supplémentaires.

Mais si le "rab" de droite avait été trop petit, alors on perd un cercle toutes les deux lignes...

oui ca peut se tester

[Ben314]

J'ai testé ça :
https://drive.google.com/file/d/0ByyHQqLyqzSudkFMNGlDQWlHNWM/edit?usp=sharing
(sous open office)

Qui teste deux façon d'empiler : soit le même nombre n de disques sur chaque ligne, soit n, n-1, n, n-1, etc...
Pour les différentes valeurs de n "cohérentes" (i.e. avec un espace entre les disque compris entre 0 et le max tel que la 3em ligne ne chevauche pas la première)

Pour le cas donné par chang (Long=5867 ; larg=2330 ; R=100), ça donne bien la dispo qu'il donne comme max : 13 lignes de 29 ou 28 disques pour un total de 371.
Pour R=99, on peut mettre 13 lignes toutes de 29 pour 377 disques.
Pour R=97, on peut toujours mettre 13 lignes de 29 pour 377 disques, mais il est préfèrable d'espacer et à ne faire que des lignes de 28 : ça permet de passer à 14 lignes, soit un total de 392.
Ça prouve déjà un truc, c'est qu'on a pas toujours interêt à en mettre le plus possible sur la "ligne du bas"

Faire gaffe quand même qu'il est fort possible qu'il y ait des erreurs dans le tableau...

[mathafou]

Bonjour,

formules, vous avez dit formules...

à condition de réduire fortememnt (très fortement) les contraintes à rien du tout certes...
(c'est à dire exclusivement à des empilements réguliers)

je vous conseille d'aller jeter un coup d'oeil aux sites dédiés à ce genre de problème pour voir que les mettre de façon irrégulière est parfois la meilleure solution :

packing center
packomania
en fait personne ne sait quelle est la meilleure solution et ce ne sont à chaque fois que des conjectures
Avec un petit (très petit) nombre de disques on peut parfois le prouver, ou tester exaustivement toutes les possibilites
Avec un plus grand nombre de disques c'est et cela restera une conjecture (le problème étant très largement NP)

[Cliffe]

Faut pas oublier qu'on est censé empiler des sacs dans un container.

[Ben314]

Après quelques essais, un truc pas vraiment étonnant, mais à noter tout de même, c'est que si on échange les dimensions du rectangle, le tableur ne trouve plus le même max.

Par exemple, pour R=91, Long=5867, Larg=2330, bien qu'on puisse en mettre jusqu'à 32 par ligne, il est préférable d'en mettre 30, 29, 30, 29... pour avoir 15 lignes et un total de 443 disques.
Mais, si on met R=91, Long=2330, Larg=5867, là, il en met 12 sur toutes les lignes (qui sont en fait les colonnes dans le dessin précédent) et il case 37 lignes pour un total de 444 disques.

Dans d'autre cas (par exemple R=100) c'est le contraire, il ne range que 363 disques si on les range "dans l'autre sens" (contre les 371 dans le sens "normal")

J'en déduirais bien qu'en général aucun des deux résultat n'est le "vrai" optimum... :triste:

[Quenton999]

Ben, merci pour le tableur. Par contre, il n'y a ni formule ni macro donc difficile à exploiter tel quel ... ^^

Pfiou en tous cas je ne m'attendais pas à ce que ce soit si complexe ! Je vais donc tacher de me débrouiller avec ces sites internet...

Merci à tous pour votre aide et votre temps !

[fatal_error]

slt Mathafou,

ui j'étais déjà tombé sur ces liens, mais j'arrive pas à trouver les algo correspondants (ou alors l'autre fait payer son bouquin...), peut-etre que je vois mal?

Sinon, voilà un fiddle pour comparer l'hexagonal avec les disques espacés en première ligne
exemple

[chan79]

Ben, merci pour le tableur. Par contre, il n'y a ni formule ni macro donc difficile à exploiter tel quel ... ^^

Pfiou en tous cas je ne m'attendais pas à ce que ce soit si complexe ! Je vais donc tacher de me débrouiller avec ces sites internet...

Merci à tous pour votre aide et votre temps !

le problème est difficile
Tout dépend des dimensions du rectangle et du rayon
Disposer en réseau hexagonal n'est pas forcément le mieux


on a intérêt à "laisser du mou" pour en caser plus

Sur mon dessin plus haut (11h10) ça me paraît plus difficile d'en mettre un de plus ...

[Ben314]

Ben, merci pour le tableur. Par contre, il n'y a ni formule ni macro donc difficile à exploiter tel quel ... ^^

Pfiou en tous cas je ne m'attendais pas à ce que ce soit si complexe ! Je vais donc tacher de me débrouiller avec ces sites internet...

Merci à tous pour votre aide et votre temps !

Sur le tableur, tu peut modifier les cases en haut à droite "Largeur", "Longueur" et "Rayon" et les formules sont dans les tableaux de droite.
Ça te met en dessous le nombre max de disque qu'il a réussi à "caser" et dans un des deux tableaux de droite, apparait en rouge le nombre n de disque qu'il a mis par ligne et le nombre m de lignes qui ont donné cet optimum (dans le tableau de gauche s'il en a mis autant par ligne et dans celui de droite s'il en a mis n,n-1,n,n-1,...)

[totodlk]

Bonjour Ben314,

J'ai essayé de télécharger ton excel et comme Quenton999 je n'ai pas de formule dans la feuille?
As tu une solution stp?
Merci d'avance,
totodlk

J'ai testé ça :
https://drive.google.com/file/d/0ByyHQqLyqzSudkFMNGlDQWlHNWM/edit?usp=sharing
(sous open office)

Qui teste deux façon d'empiler : soit le même nombre n de disques sur chaque ligne, soit n, n-1, n, n-1, etc...
Pour les différentes valeurs de n "cohérentes" (i.e. avec un espace entre les disque compris entre 0 et le max tel que la 3em ligne ne chevauche pas la première)

Pour le cas donné par chang (Long=5867 ; larg=2330 ; R=100), ça donne bien la dispo qu'il donne comme max : 13 lignes de 29 ou 28 disques pour un total de 371.
Pour R=99, on peut mettre 13 lignes toutes de 29 pour 377 disques.
Pour R=97, on peut toujours mettre 13 lignes de 29 pour 377 disques, mais il est préfèrable d'espacer et à ne faire que des lignes de 28 : ça permet de passer à 14 lignes, soit un total de 392.
Ça prouve déjà un truc, c'est qu'on a pas toujours interêt à en mettre le plus possible sur la "ligne du bas"

Faire gaffe quand même qu'il est fort possible qu'il y ait des erreurs dans le tableau...

[Ben314]

J'ai essayé de télécharger ton excel et comme Quenton999 je n'ai pas de formule dans la feuille?
As tu une solution stp?
Merci d'avance,
totodlk

Ben non : les formules sont bien dans la feuille (dans les colonnes de droite).
Après, c'est pas du excel, mais du Open Office, mais ça doit pas changer grand chose.
Y'a peut-être le formatage conditionnel qui passe pas, mais en fait j'en sais rien.

[totodlk]

Ben non : les formules sont bien dans la feuille (dans les colonnes de droite).
Après, c'est pas du excel, mais du Open Office, mais ça doit pas changer grand chose.
Y'a peut-être le formatage conditionnel qui passe pas, mais en fait j'en sais rien.

OK merci de ta réponse mais cela ne fonctionne pas dommage.
Bonne journée,