Petits rectangles dans grand cercle

Bon, voilà mon souci :
Je dois écrire un algorithme qui optimise le placement de rectangles dans un cercle.
Je connais:

  • le rayon du cercle
  • la largeur et la hauteur des rectangles

Le but est d’arriver à placer le plus possible de rectangles entiers dans le cercle, et à donner en sortie les coordonnées de chacun des rectangles par rapport au centre du cercle. En fait, il suffit d’avoir la coordonnée du premier.
Un petit dessin pour mieux comprendre :

En fait, je sais pas vraiment par où commencer, ni quoi googliser (si, ça se dit !)… Des idées ?

(Je suis bourré)<= donc je vais pas être super clair dans mes idées :stuck_out_tongue: (et en plus elles seront fausses)(et elle von servir a rien, mais ça maidera a désouler)

_petit_a) Tu auras plein de calculs de trigo à faire, et tu vas les trouver nulle part.

petit:stuck_out_tongue: A mon avis le point de départ est la symétrie de ton cercle, tu auras 2 cas possible:
b1) Le " diamètre vertical" passe entre deux rectangle.
b2) Le « diamètre vertical » passe au millieu d’un rectangle.

_petit_c) En connaissant ces 2 cas, tu as le choix
c1) Tu simules: tu fais 2-3 boucles en plaçant le premier rectangle selon le cas 1 ou le cas 2 et tu prend le meilleur (=> tu aimes le « code »)
c2) Tu calcules: tu prends une grosse feuille, une grosse calculatrice et tu sort une « formule magique » qui te permet de savoir ou tu commences (=> tu aimes les maths).

La grande question est: Est-ce que la formule magique existe?

Mon avis: Si ton prof aime les maths, tente de trouver la formule magique.
Sinon, simules, tu vas perdre moins de neurones.

Bonne nuit :stuck_out_tongue:

edit: Essaie les calculs quand même, cherche pas des schémas trop compliqués c’est que des cercles et des rectangles. C’est super symétrique. Avec 2-3 gros dessins tu devrais t’en tirer assez facilement.

edit du matin: Faut vraiment que j’arrête de parler info à 4h du mat’ moi… Y’a plein plein de conneries la dedans… 'solé :stuck_out_tongue:

Clair. Le mec qui a ce genre des question en entretien saute direct sur le code « pour simuler » sans chercher a bien comprendre le probleme et comment l’approcher, ca s’approche fortement du comportement disqualificatoire :stuck_out_tongue:

J’ai déjà fait quelques recherches (et implémentations) sur le bin packing et le strip packing. J’ai pas été très loin car un résultat « satisfaisant » me suffisait. Ton problème y ressemble un peu.

La première étape serait de trouver le nom exact du problème, si il est connu, à partir de là Google va te dénicher tout ce dont tu peux rêver. Mais même si il doit exister des articles bien fouillés sur le sujet, voici quelques principes de base qui semblaient ne pas trop mal marcher pour mes problèmes de packing:

Moi j’y ai été de façon heuristique, l’idée est de classer tes rectangles par taille décroissante, et de d’abord mettre les gros en place, et ensuite essayer de combler les trous avec les petits, en prenant le plus petit trou disponible de taille suffisante. Ensuite, lorsqu’on essaie de mettre un petit rectangle dans un trou, on peut aussi essayer de le mettre dans un trou trop petit, en « poussant » ce qui se trouve alentours, mais là ça devient un peu chaud pour satisfaire en même temps toutes les contraintes générées par ce mouvement.

Un collègue y avait été avec un algo génétique, ça donnait des résultats un peu meilleurs, mais c’était globalement plus lent que mon système. Ca peut être une piste à explorer aussi.

Ah, un dernier point que tu ne précises pas dans ta question : est-ce que les rectangles sont orientés sur les axes, ou bien peuvent-ils tourner sur eux-même ? Dans ce dernier cas, bon courage :stuck_out_tongue:

edit: oh un autre truc, je me demande si j’ai pas tout compris de travers… tes rectangles, ils ont tous la même taille ?

Ouh la ouh la ouh la !
Ca a l’air super intéressant ton approche, mais je cherche pas si compliqué : mes rectangles ont tous la même taille (connue) et mon cercle a également une taille connue. De plus, ils ne peuvent pas tourner.
Ceci dit, je pense que l’idée est un peu la même que ce que tu avais fait : comment tu places tes gros rectangles au début ?

Je veux bien essayer la méthode itérative, mais comment démarrer ? Je place mon repère de coordonnées sur un point du cecle et je place des rectangles jusqu’à ce qu’ils ne rentrent plus puis je passe à la ligne suivante ?

Alors pour placer les rectangles, moi je commencais par remplir les coins… Dans le cas du cercle, cette méthode risque de ne pas fonctionner :stuck_out_tongue: Disons que je pense que j’essaierai tout d’abord en divisant le cercle en 4 en son milieu, et j’utiliserai les 4 coins ainsi créés.

J’avais écrit un gros pavé de texte, mais tout en tapant je pense avoir trouvé la bonne approche. Etant donné que la solution va forcément être symétrique par rapport au centre du cercle, il n’y a que 4 façons de positionner le rectangle « du milieu ». Pour chaque axe, soit le centre du cercle tombe sur le côté du rectangle, soit il tombe au milieu. Attends, je vais faire un petit dessin et je reviens.

Bon, ensuite tous les autres rectangles vont venir s’aligner sur ce rectangle « central ». Ca ne fait que 4 cas à tester pour trouver lequel est optimal en nombre de rectangles. Et en cherchant un peu, y’a sûrement moyen de trouver une petite formule qui va déterminer ce cas optimal du premier coup.

J’espère que ça t’aide, et que je ne suis pas en train de t’envoyer sur une mauvaise piste, j’avoue que j’ai pas testé, mais ça me semble assez logique comme ça.

Cool cool cool, m’en vais tester tout ça puis je vous tiens au courant.
Merci ! :stuck_out_tongue:

Juste une idée du dimanche aprem :
Si tu considères ton cercle comme un carré de ton diamètre, tu divises ton carré en une grille de n rectangle collés un contres les autres. Ensuite, tu plaque ta grille contre ton cercle et tu regardes le nombre de rectangles entiers dans le cercle. Après tu peux toujours déplacer ta grille (rectangle centré au milieu du cercle, centré horizontal/décalé vertical, centré vertical, décalé horizontal) pour trouver un optimum.
Méthode bourrine, mais ça doit marcher.

Edit : il vaut surement augmenter un peu (genre diamètre + longueur rectangle) la taille de ta grille pour tester les différentes combinaisons

Perso je commencerais en plaçant le premier rectangle au « sommet » du cercle. Ca laisse que deux possibilité de commencer Tu peux trouver les coordonné du coin haut gauche en 2 coup de trigo, ça devrait pas être sorcier.

Et la suite est peut-etre une enorme connerie.

Il me semble que que tu peux choisir ton point de départ par rapport au dimension de ton rectangle.

Si il est plus haut que large, il sera décallé à gauche (le premier dessin).
Si c’est un carré ou qu’il est plus large que haut il sera centré(le deuxieme dessin).

C’est sans garantie. C’est juste un « sentiment », et ça me paraitrais presque logique. Mais j’ai rien calculé, ni tester. Donc voilà.

//Fin de la connerie

Par contre si tu peux nous donner un feedback pour savoir .si j’ai dit que des conneries ou pas ça serait cool :stuck_out_tongue:

(a ben tiens on peut plus joindre d’images au messages pakewl)

je suis pas sûr que le meilleur placement soit toujours avec tous les rectangles dans le même sens (IIIIII), mais peut être aussi des (III–III) parfois, non ?

(je suis une brute en ASCII art, je sais ^^)

PS : poy Isha ^^

Comme disait Drealmer, je vote pour des algorithmes d’optimisation.
On a eu un projet d’optimisation de reseaux en cours, a resoudre avec tout ce qu’on veut (Genetique, Essaims, Recuit simule, MonteCarlo etc.). C’est relativement facile a mettre en place et globalement tres puissant.
Recherche du cote des Heuristiques, je pense que c’est comme ca que tu obtiendras le meilleur resultat.

Après avoir passé une partie de l’aprem à dessiner des petits rectangles dans des cercles, on m’a emmené à l’asile psychiatrique j’ai déduis quelques petits trucs :
Drealmer> Bon ben en fait ton postulat de départ disant que les carrés sont forcément symétriques par rapport au centre n’a pas l’air correct. J’ai édité mon premier post avec un petit schéma où on voit que la méthode de kaneloon est pas mal.

kaneloon> Je sens que je vais pleurer ma race pour coder ça, mais je pense que je vais tenter le coup

Luka> Poy copain dr00d :stuck_out_tongue:

JakeGrafton> Tu aurais pas des exemples concrets sous la main (liens) ?

Edit: Ah, oui : super ASCII art lucasbfr, mais on ne peut pas changer l’orientation des rectangles…

erf… Dans ce cas, je vois rien d’autre que tester « toutes » les possibilités de placement entre 0 et longueur/2 et 0 et largeur/2 :stuck_out_tongue:

pour compter les rectangles, le mieux serait de partir de haut à gauche (-rayon+decalx, rayon+decaly) et de compter tous les rectangles dont les 4 coins sont dedans.

PS : oué je sais c’est brutasse, mais j’avoue ne rien voir de malin

edit : je racontais nawak, si les 4 coins sont dans le rond c’est bon en fait…

Je serais fabriquant de processeur , ca me semblerait un algo ultra nécessaire.
( le cristal de Si poussant rond, au moins ily a quelques années).
Donc deux possibilités :

  • C’est ta finalité
  • Ca existe est c’est une piste pour googliser.

Sinon, le rapport de ton rectangle il est quelquonque ou c’est un rapprot denombre entier ?

Déja je te déteste: poser ça un jour avant la reprise des cours c’est méchant, j’vois des rectangles et des rond partout et j’arrive pas a m’endormir :stuck_out_tongue:

Je crois que je commence d’approcher d’un raisonnement pas mal, mais comme j’ai déjà dis assez de connerie sur ce thread, je vais attendre encore un peu avant de parler.

Je pense juste que les colonies de fourmies et tout ce genre d’heuristiques sont un peu trop compliqué pour ce problème, et je crois que la solution est plus simple.

Pour les liens en question commence par wikipedia avec le mot heuristiques et ballades toi dans les liens tu devrais trouver du contenu.

Le principe d’un algo gen c’est de creer une famille de solutions, de les faire se “reproduire” entre elles pour emuler mes “bonnes” solutions pendant que tu cherches a introduire des solutions completement differentes pour elargir ton panel de solutions (principe des reproductions/mutations). Le tout est de bien representer la forme de ta solution pour pouvoir facilement les croiser; et c’est souvent la que ca coince. Si tu ne choisis pas un truc ultime, ca peut vite devenir mechament lourd a calculer. Apres ca, tu laisse tourner le temps qu’il faut et hop tu as une “bonne” solution.

Le hic c’est que je passe le pb dans tous les sens depuis 1/2 heure et que je vois pas comment l’implementer facilement …

J’editerais ou posterais a nouveau quand j’aurais trouve une (bonne) idee …

Edit:
En effet, ca ressemble etrangement a un probleme d’agencement de Microprocesseurs sur des “Wafers”. Or que ce soit avec des carres ou des rectangles ils l’agencent suivant une grille partant du milieu. Soit :



Comme vous pouvez le voir, c’est bien suivant une grille. Il faudrait faire tourner des heuristiques pour en etre certain ou le resoudre de maniere mathematique (et j’ai absolument pas le courage d’essayer la), mais ca ne parait pas idiot comme facon de faire.

Tu peux donc tester deux config en partant :

  • un rectangle centre sur le centre du cercle
  • un rectangle dans le coin d’un des 1/4 de cercles, et en fonction du ratio rayon/largeur ou hauteur du rectangle, l’un ou l’autre peut etre le plus interessant …

L’ idee de la grille est pas mal du tout mais il y a un cas où elle n’ est pas optimale du tout (un rectangle avec L tres grand devant l).
Si on utilise une technique de grille au niveau des wafer c’ est parce que jsutement ce cas ne se presente pas :stuck_out_tongue: (bon ca doit aussi faciliter la decoupe mais avec le matos d’ aujourd’hui ca ne devrait pas poser probleme de faire des decoupes un peu plus compliquer :P)

Ca dépend, si les rectangles doivent être alignés (comme dans le dessin du premier post), ta proposition peut ne pas mener à la solution optimale. (je ferais bien un dessin pour illustrer mon point, mais je suis au boulot là, et si quelqu’un me demande ce que je fais, je vais avoir du mal à justifier :stuck_out_tongue: )

D’un point de vue mathématique, il faudrait trouver 2 suites l’une croissante l’autre décroissante qui convergent vers le cercle.
u0=Le carré entier qui est contenu dans le cercle.
v0=Le carré entier qui contient le cercle.

(il faut peut être simplifier la problématique avec des carrés et généraliser ensuite).