Quel algorithme peut être utilisé pour emballer des rectangles de différentes tailles dans le plus petit rectangle possible d'une manière assez optimale?

J'ai un tas d'objets rectangulaires que je dois emballer dans le plus petit espace possible (les dimensions de cet espace devraient être des puissances de deux).

Je connais différents algorithmes d'emballage qui emballeront les articles aussi bien que possible dans un espace donné, mais dans ce cas, j'ai besoin de l'algorithme pour déterminer la taille de cet espace.

Par exemple, disons que j'ai obtenu les rectangles suivants

• 128 * 32
• 128 * 64
• 64 * 32
• 64 * 32

Ils peuvent être emballés dans un espace 128 * 128

 _________________
| 128 * 32 |
| ________________ |
| 128 * 64 |
| |
| |
| ________________ |
| 64 * 32 | 64 * 32 |
| _______ | ________ |

Cependant, s'il y avait aussi un 160 * 32 et un 64 * 64, il faudrait un espace de 256 * 128

 ________________________________
| 128 * 32 | 64 * 64 | 64 * 32 |
| ________________ | | _______ |
| 128 * 64 | | 64 * 32 |
| | _______ | _______ |
| | |
| ________________ | ___ |
| 160 * 32 | |
| ____________________ | ___________ |

Quels algorithmes existe-t-il pour emballer un tas de rectangles et déterminer la taille requise pour le conteneur (à une puissance de 2 et dans une taille maximale donnée pour chaque dimension)?

La solution de premier passage rapide et sale est toujours une excellente solution pour commencer, à titre de comparaison si rien d'autre.

Placement gourmand du grand au petit.

Mettez le plus grand rectangle restant dans votre zone emballée. S'il ne peut pas rentrer n'importe où, placez-le dans un endroit qui étend le moins possible la région du pack. Répétez jusqu'à ce que vous ayez terminé avec le plus petit rectangle.

Ce n'est pas parfait du tout mais c'est facile et une belle base de référence. Il emballerait toujours parfaitement votre exemple d'origine et vous donnerait également une réponse équivalente pour le second.

Voir cette page sur le projet ARC pour un aperçu des solutions, il y a un compromis entre complexité / temps de mise en œuvre et optimalité, mais il existe un large éventail d'algorithmes parmi lesquels choisir.

Voici un extrait des algorithmes:

1. Algorithme de hauteur décroissante de premier ajustement (FFDH)
   FFDH emballe l'élément suivant R (en hauteur non croissante) au premier niveau où R s'adapte. Si aucun niveau ne peut accueillir R, un nouveau niveau est créé.
   Complexité temporelle de FFDH: O (n · log n).
   Rapport d'approximation: FFDH (I) <= (17/10) · OPT (I) +1; la borne asymptotique de 17/10 est serrée.

2. Algorithme de hauteur décroissante Next-Fit (NFDH)
   NFDH emballe l'élément suivant R (en hauteur non croissante) au niveau actuel si R correspond. Sinon, le niveau actuel est "fermé" et un nouveau niveau est créé.
   Complexité temporelle: O (n · log n).
   Rapport d'approximation: NFDH (I) <= 2 · OPT (I) +1; la limite asymptotique de 2 est serrée.

3. Algorithme de hauteur décroissante (BFDH) le
   mieux ajusté BFDH place l'élément suivant R (en hauteur non croissante) au niveau, parmi ceux qui peuvent accueillir R, pour lesquels l'espace horizontal résiduel est le minimum. Si aucun niveau ne peut accueillir R, un nouveau niveau est créé.

4. Algorithme inférieur gauche (BL)
   Éléments BL de premier ordre par largeur non croissante. BL emballe l'article suivant aussi près du bas qu'il conviendra, puis aussi près de la gauche que possible sans chevaucher aucun article emballé. Notez que BL n'est pas un algorithme de compression orienté niveau.
   Complexité temporelle: O (n ^ 2).
   Rapport d'approximation: BL (I) <= 3 · OPT (I).

5. Algorithme Baker-Up-Down (UD)
   UD utilise une combinaison de BL et une généralisation de NFDH. La largeur de la bande et des articles est normalisée de sorte que la bande soit de largeur unitaire. UD ordonne les articles en largeur non croissante, puis divise les articles en cinq groupes, chacun avec une largeur dans la plage (1/2, 1], (1 / 3,1 / 2], (1 / 4,1 / 3 ], (1 / 5,1 / 4], (0,1 / 5]. La bande est également divisée en cinq régions R1, ···, R5. Fondamentalement, certains éléments de largeur dans la plage (1 / i + 1, 1 / i], pour 1 <= i <= 4, sont emballés dans la région Ri par BL. Puisque BL laisse un espace de largeur croissante de haut en bas sur le côté droit de la bande, UD profite de cet avantage en premier emballer l'article à Rj pour j = 1, ···, 4 (dans l'ordre) de haut en bas. S'il n'y a pas un tel espace, l'article est emballé à Ri par BL. Enfin, les articles de taille au plus 1/5 sont compressés dans les espaces de R1, ···, R4 par l'algorithme (généralisé) NFDH.
   Rapport d'approximation: UD (I) <= (5/4) · OPT (I) + (53/8) H, où H est la hauteur maximale des articles; la limite asymptotique de 5/4 est serrée.

6. L'algorithme d'ajustement inverse (RF)
   RF normalise également la largeur de la bande et des articles de sorte que la bande soit de largeur unitaire. RF empile d'abord tous les articles de largeur supérieure à 1/2. Les articles restants sont triés en hauteur non croissante et seront emballés au-dessus de la hauteur H0 atteinte par ceux supérieurs à 1/2. RF répète ensuite le processus suivant. En gros, RF emballe les articles de gauche à droite avec leur bas le long de la ligne de hauteur H0 jusqu'à ce qu'il n'y ait plus de place. Emballe ensuite les articles de droite à gauche et de haut en bas (appelé niveau inversé) jusqu'à ce que la largeur totale soit d'au moins 1/2. Ensuite, le niveau inverse est abaissé jusqu'à ce que (au moins) l'un d'eux touche un élément ci-dessous. La liste déroulante est en quelque sorte répétée.
   Rapport d'approximation: RF (I) <= 2 · OPT (I).

7. L'algorithme de Steinberg L'algorithme de
   Steinberg, noté M dans l'article, estime une limite supérieure de la hauteur H requise pour emballer tous les articles de telle sorte qu'il soit prouvé que les articles d'entrée peuvent être emballés dans un rectangle de largeur W et de hauteur H. définir sept procédures (avec sept conditions), chacune pour diviser un problème en deux plus petites et les résoudre récursivement. Il a été démontré que tout problème traitable remplit l'une des sept conditions.
   Rapport d'approximation: M (I) <= 2 · OPT (I).

8. Algorithme Split-Fit (SF) SF divise les éléments en deux groupes, L1 avec une largeur supérieure à 1/2 et L2 au plus 1/2. Tous les articles de L1 sont d'abord emballés par FFDH. Ensuite, ils sont disposés de sorte que tous les articles dont la largeur est supérieure à 2/3 soient inférieurs à ceux dont la largeur est au maximum de 2/3. Cela crée un rectangle R d'espace de largeur 1/3. Les éléments restants dans L2 sont ensuite emballés dans R et l'espace au-dessus de ceux emballés dans L1 à l'aide de FFDH. Les niveaux créés dans R sont considérés comme inférieurs à ceux créés au-dessus de l'emballage de L1.
   Rapport d'approximation: SF (I) <= (3/2) · OPT (I) + 2; la limite asymptotique de 3/2 est serrée.

9. Algorithme de Sleator L'algorithme de
   Sleater comprend quatre étapes:

   1. Tous les articles de largeur supérieure à 1/2 sont emballés les uns sur les autres dans le bas de la bande. Supposons que h0 est la hauteur de l'emballage résultant. Tout emballage ultérieur se produira au-dessus de h0.

   2. Les éléments restants sont classés par hauteur non croissante. Un niveau d'articles est emballé (dans l'ordre de hauteur non croissante) de gauche à droite le long de la ligne de hauteur h0.

   3. Une ligne verticale est ensuite tracée au milieu pour couper la bande en deux moitiés égales (notez que cette ligne peut couper un article partiellement emballé dans la moitié droite). Tracez deux segments de ligne horizontale de longueur une moitié, un sur la moitié gauche (appelée la ligne de base gauche) et un sur la moitié droite (appelée la ligne de base droite) aussi bas que possible de sorte que les deux lignes ne croisent aucun élément.

   4. Choisissez la ligne de base gauche ou droite qui est d'une hauteur inférieure et placez un niveau d'articles dans la moitié correspondante de la bande jusqu'à ce que l'article suivant soit trop large.

   Une nouvelle ligne de base est formée et l'étape (4) est répétée sur la ligne de base inférieure jusqu'à ce que tous les articles soient emballés.
   Complexité temporelle: O (n · log n).
   Le rapport d'approximation de l'algorithme de Sleator est de 2,5, ce qui est serré.

Jetez un œil aux problèmes d'emballage . Je pense que le vôtre tombe sous «emballage bin 2D». Vous devriez être en mesure d'apprendre beaucoup de solutions à cela et à d'autres problèmes d'emballage.

Voir aussi: Emballage de données d'images rectangulaires dans une texture carrée.

Il existe une littérature abondante sur ce problème. Une bonne heuristique gourmande consiste à placer des rectangles de la plus grande zone à la plus petite dans la première position disponible vers le bas et la gauche du conteneur. Pensez à la gravité tirant tous les articles vers le coin inférieur gauche. Pour une description de ce google "Emballage Chazelle en bas à gauche".

Pour des solutions optimales, les techniques de pointe peuvent emballer plus de 20 rectangles en quelques secondes. Huang a un algorithme qui sépare le problème de trouver la plus petite boîte englobante englobante du problème de décider si un ensemble de rectangle peut ou non tenir dans une boîte englobante d'une taille spécifique. Vous donnez à son programme un ensemble de rectangles, et il vous indique la plus petite boîte englobante englobante requise pour les emballer.

Pour votre cas, votre boucle extérieure doit itérer du plus petit cadre de délimitation possible vers le haut (la largeur et la hauteur augmentant successivement par deux puissances). Pour chacune de ces boîtes englobantes, testez pour voir si vous pouvez trouver un emballage pour vos rectangles. Vous obtiendrez un tas de réponses «non», jusqu'à la première réponse «oui», qui sera garantie d'être la solution optimale.

Pour la boucle interne de votre algorithme - celle qui répond "oui" ou "non" à une boîte englobante de taille spécifique, je rechercherais la référence Huang et implémenterais simplement son algorithme. Il inclut de nombreuses optimisations en plus de l'algorithme de base, mais vous n'avez vraiment besoin que de la viande et des pommes de terre de base. Étant donné que vous souhaitez gérer les rotations, à chaque point de branchement au cours de votre recherche, essayez simplement les rotations et les retours en arrière lorsque les deux rotations ne donnent pas de solution.

Je suis assez certain que c'est un problème NP-difficile , donc, pour une solution optimale, vous devez implémenter un algorithme de retour en arrière qui essaie toutes les combinaisons possibles.

La bonne nouvelle est qu'en raison de la nécessité d'emballer des rectangles 2D dans un espace 2D limité, vous pouvez élaguer de nombreuses possibilités dès le début, donc ce n'est peut-être pas si mal.

Ce dont vous avez besoin est sur https://github.com/nothings/stb/blob/master/stb_rect_pack.h

échantillon:

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}

Une solution générale n'est pas triviale (les mathématiques parlent de complètement impossible).
En général, les gens utilisent un algorithme génétique pour essayer des combinaisons possibles, mais vous pouvez faire assez bien en plaçant d'abord la plus grande forme puis en essayant différents endroits pour le prochain plus grand et ainsi de suite.