Quel algorithme peut être utilisé pour l'emballage des rectangles de différentes tailles dans le petit rectangle possible dans un assez manière optimale?
Ive a obtenu un tas d'objets rectangulaires dont j'ai besoin pour emballer dans le plus petit espace possible (les dimensions de cet espace doivent être des puissances de deux).
Je suis au courant des diverses emballage des algorithmes qui vont emballer les objets aussi bien que possible dans un espace donné, mais dans ce cas j'ai besoin de l'algorithme pour déterminer comment grand que l'espace doit être aussi bien.
Par exemple dire que Ive a obtenu à la suite de rectangles
- 128*32
- 128*64
- 64*32
- 64*32
Ils peuvent être emballés dans un 128*128 espace
_________________ |128*32 | |________________| |128*64 | | | | | |________________| |64*32 |64*32 | |_______|________|
Si toutefois il y avait aussi un 160*32 et un 64*64 celui qu'il aurait besoin d'un 256*128 espace
________________________________ |128*32 |64*64 |64*32 | |________________| |_______| |128*64 | |64*32 | | |_______|_______| | | | |________________|___ | |160*32 | | |____________________|___________|
Quels algorithmes sont là-bas qui sont en mesure d'emballer un bouquet de rectangles et de déterminer la taille requise pour le conteneur (à une puissance de 2, et à l'intérieur d'une taille maximale pour chaque dimension)?
- Je suis à droit de vote de cette question, non seulement parce que c'est intéressant, mais les rectangles sont assez.
- +1 c'est exactement la question que j'aurais demandé pour l'emballage des glyphes de police dans une texture, mais mieux présenté que rien de ce que j'aurais fait
- N'est-ce pas la deuxième solution n'est pas optimal? Ne devrait-elle pas être de 128 par 224?
- "les dimensions de cet espace doivent être des puissances de deux", Donc il ne fait pas de différence, pour ce que cela a été/est pour que je ne peut pas supposer non-puissance de deux est soutenu sans réserve par le matériel sous-jacent.
- De toute façon il fait l'algorithme le plus simple en fin de compte(essayez de répondre à tous en 32x32, si pas alors essayez de 64x32, puis de 64 x 64, 128 x 64, etc) 🙂
- Peters: j'en avais besoin aussi bien pour les polices de caractères pour mon jeu 😀
- Voir jair.org/media/3735/live-3735-6794-jair.pdf
- J'ai mis un type de force brute solution ici stackoverflow.com/a/47698424/1641247
Vous devez vous connecter pour publier un commentaire.
Rapide et sale de premier passage de la solution est toujours un excellent point de départ, car une comparaison si de rien d'autre.
Gourmand placement de grand à petit.
Mettre le plus grand rectangle restant dans votre pique-zone. Si elle ne rentre pas n'importe où, la placer dans un lieu qui s'étend le pack de la région aussi peu que possible. Répétez jusqu'à ce que vous avez terminé avec le plus petit rectangle.
Il n'est pas parfait du tout, mais il est facile et une belle ligne de base. Il serait encore emballer votre exemple d'origine parfaitement, et vous donner un équivalent de réponse pour le deuxième aussi.
Voir cette page sur l'ARC de projet pour l'étude des solutions, il y a un compromis entre la complexité de mise en œuvre/du temps et de l'optimalité, mais il ya une large gamme d'algorithmes pour choisir.
Voici un extrait des algorithmes:
Premier Ajustement de la Diminution de la Hauteur (FFDH) algorithme
FFDH packs le prochain élément de R (non-augmentation de la hauteur) sur le premier niveau où R correspond. Si aucun niveau peut accueillir R, un nouveau niveau est créé.
Le temps de la complexité de la FFDH: O(n·log n).
Rapprochement ratio: FFDH(I)<=(17/10)·OPT(I)+1; asymptotique lié de 17/10 est serré.
Next-Fit, la Diminution de la Hauteur (NFDH) algorithme
NFDH packs le prochain élément de R (non-augmentation de la hauteur) sur le niveau actuel si R s'adapte. Sinon, le niveau actuel est "fermé" et un nouveau niveau est créé.
Le temps de la complexité: O(n·log n).
Rapprochement ratio: NFDH(I) <= 2·OPT(I)+1; asymptotique lié de 2 est serré.
Meilleur Ajustement de la Diminution de la Hauteur (BFDH) algorithme
BFDH packs le prochain élément de R (non-augmentation de la hauteur) sur le niveau, parmi ceux qui peuvent accueillir de R, pour lequel le résidu d'espace horizontal est le minimum. Si aucun niveau peut accueillir R, un nouveau niveau est créé.
Bas-Gauche (BL) Algorithme
BL première commande d'articles par la non-augmentation de la largeur. BL packs de l'élément suivant au plus près de la bas car il convient et puis aussi proche de la gauche, comme il peut aller sans chevauchement avec tout emballés. Notez que les BL n'est pas un niveau orientée sur l'emballage de l'algorithme.
Le temps de la complexité: O(n^2).
Rapprochement ratio: BL(I) <= 3·OPT(I).
De boulanger Haut-Bas (UD) algorithme
UD utilise une combinaison de BL et une généralisation de NFDH. La largeur de la bande et les éléments sont normalisées, de sorte que la bande est de largeur d'unité. UD commandes les éléments de non-augmentation de la largeur et divise ensuite les éléments en cinq groupes, chacun avec la largeur de la gamme (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. La bande est également divisé en cinq régions, R1, ··· , R5. Fondamentalement, certains éléments de la largeur de la plage (1/i+1, 1/i], pour 1 <= i <= 4, sont entassés dans la région Ri par BL. Depuis BL laisse un espace à l'augmentation de la largeur de haut en bas sur le côté droit de la bande de gaza, UD en profite par le premier emballage de l'élément Rj pour j = 1, ··· , 4 (dans l'ordre) du haut vers le bas. Si ce n'est pas l'espace, l'article est emballé à Ri par BL. Enfin, les éléments de la taille de la plupart 1/5 sont emballés à l'espace dans R1, ··· , R4 par l' (généralisée) NFDH algorithme. S'il n'y avait pas d'espace dans ces régions, l'article est emballé pour R5 à l'aide de NFDH.
Rapprochement ratio: UD(I) <= (5/4) · OPT(I)+(53/8)H, où H est la hauteur maximale des éléments; l'asymptotique lié 5/4 est serré.
Inverse-fit (RF) de l'algorithme
RF normalise également la largeur de la bande et les objets de sorte que la bande est de largeur d'unité. RF d'abord les piles de tous les éléments de largeur supérieure à 1/2. Les autres éléments sont triés dans la non-augmentation de la hauteur et seront emballés au-dessus de la hauteur H0 atteint par les personnes de plus de 1/2. Ensuite RF répète le processus suivant. Grosso modo, RF packs éléments de gauche à droite avec leurs bas le long de la ligne de hauteur H0 jusqu'à ce qu'il n'y a plus de place. Puis packs éléments de droite à gauche et de bas en haut (appelé inverse de niveau) jusqu'à ce que la largeur totale est d'au moins 1/2. Alors l'inverse de niveau est tombé vers le bas jusqu'à (au moins) l'un d'eux touche un élément ci-dessous. La liste déroulante est d'une certaine manière répétée.
Rapprochement ratio: RF(I) <= 2·OPT(I).
Steinberg algorithme
Steinberg de l'algorithme, que l'on note M dans l'étude, les estimations de la limite supérieure de la hauteur H, nécessaires pour emballer tous les articles, tel qu'il a été prouvé que les éléments d'entrée peut être emballé dans un rectangle de largeur W et de hauteur H. Ils ont ensuite définir sept procédures (avec sept conditions), chacun de diviser un problème en deux plus petits et de les résoudre de manière récursive. Il a été montré que toute docile problème satisfait à l'une des sept conditions.
Rapprochement ratio: M(I) <= 2·OPT(I).
Split-Ajustement de l'algorithme (SF)
SF divise éléments en deux groupes, L1 avec une largeur de plus de 1/2 et L2 au plus 1/2. Tous les éléments de L1 sont d'abord emballé par la FFDH. Ensuite, ils sont disposés de sorte que tous les éléments avec une largeur de plus de 2/3 sont en dessous de celles avec une largeur à la plupart des 2/3. Cela crée un rectangle R de l'espace avec une largeur de 1/3. Les autres éléments de L2 sont ensuite conditionnés à la R et de l'espace au-dessus de ceux emballés avec de la 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 la L1.
Rapprochement ratio: SF(I) <= (3/2) ·OPT(I) + 2; l'asymptotique lié de 3/2 est serré.
Sleator de l'algorithme
Sleater de l'algorithme se compose de quatre étapes:
Tous les éléments de largeur supérieure à 1/2 sont emballés sur le dessus de l'un l'autre dans le bas de la bande. Supposons que h0 est la hauteur de la l'emballage de Tous leur emballage va se produire au-dessus de h0.
Éléments restants sont commandés par la non-augmentation de la hauteur. Un niveau d'objets sont emballés (non en augmentant la hauteur de l'ordre de la gauche vers la droite le long de la ligne de hauteur h0.
Une ligne verticale est ensuite établi au moyen de couper la bande en deux moitiés égales (notez que cette ligne peut couper un élément qui est emballé en partie dans la moitié de droite). Dessinez deux horizontale des segments de ligne de la longueur de la moitié, de l'autre côté de la gauche de la moitié (appelé la gauche de la ligne de base) et une dans la moitié droite (qu'on appelle le droit de base) aussi bas que possible, de sorte que les deux lignes ne se croisent pas n'importe quel élément.
Choisir la gauche ou la droite ligne de base qui est d'une hauteur inférieure et pack un niveau d'éléments dans la moitié de la bande jusqu'à l'élément suivant est trop large.
Une nouvelle ligne de base est formé à l'Étape (4) est répété sur le bas de la ligne de base jusqu'à ce que tous les articles sont emballés.
Le temps de la complexité: O(n ·log n).
Le rapprochement ratio de Sleator de l'algorithme est de 2,5 qui est serré.
Ont un coup d'oeil à l'emballage des problèmes. Je pense que le vôtre tombe sous '2D bin packing.' Vous devriez être en mesure d'apprendre beaucoup de solutions et d'autres problèmes d'empaquetage.
Voir aussi: Emballage rectangulaire des données d'image dans un carré de texture.
Il existe une vaste littérature sur ce problème. Une bonne gourmande heuristique est de placer les rectangles de surface la plus grande à la plus petite, dans la première position disponible vers le bas et à gauche du conteneur. Pensez à la gravité qui attire tous les objets dans le coin inférieur gauche. Pour une description de ce google "Chazelle en bas à gauche de l'emballage.
De solutions optimales, l'état-de-la-art des techniques d'pack de plus de 20 rectangles en quelques secondes. Huang a un algorithme qui sépare le problème de trouver le plus petit joignant la boîte englobante de le problème de décider si oui ou non un ensemble de rectangle qui peuvent tenir dans une boîte englobante d'une taille spécifique. Vous donner à son programme un ensemble de rectangles, et il vous indique le plus petit joignant la boîte englobante nécessaire de les emballer.
Pour votre cas, votre boucle externe doit effectuer une itération à partir de la plus petite boîte englobante haussière (avec la largeur et la hauteur successivement à l'augmentation des puissances de deux). Pour chacune de ces boîtes englobantes, test pour voir si vous pouvez trouver un emballage pour votre rectangles. Vous obtiendrez un tas de "non-réponses", jusqu'à ce que la première réponse "oui", qui seront garantis pour être la solution optimale.
De la boucle interne de votre algorithme -- celui qui répond "oui" ou "non" pour une matrice de taille spécifique, je voudrais regarder le Huang de référence et de mettre en œuvre son algorithme. Il comprend un grand nombre d'optimisations sur le dessus de l'algorithme de base, mais vous ne vraiment besoin de la viande et des pommes de terre. Puisque vous voulez gérer les rotations, à chaque point de branchement au cours de votre recherche, essayez simplement de deux rotations et de revenir en arrière lorsque les deux rotations n'aboutissent pas à une solution.
Je suis assez certain que c'est un problème NP-difficile, de sorte que, pour une solution optimale, vous auriez à mettre en œuvre un algorithme de backtracking qui essaie toutes les combinaisons possibles.
La bonne nouvelle est qu'en raison de la nécessité de pack 2D rectangles limitée à l'espace 2D, vous pouvez le tailler beaucoup de possibilités dès le début, il pourrait ne pas être si mauvais QUE ça.
Ce que vous avez besoin est
https://github.com/nothings/stb/blob/master/stb_rect_pack.h
exemple:
Une solution générale est non-trivial (les mathématiques parlent d'complètement ****ing impossible)
Généralement les gens utilisent un algorithme génétique pour essayer de combinaisons possibles, mais vous pouvez le faire raisonnablement bien par justing de mettre la plus grande forme en premier et ensuite essayer différents endroits pour le deuxième et ainsi de suite.
Je suis en utilisant l'une à partir de:
https://codereview.stackexchange.com/questions/179565/incremental-2d-rectangle-bin-packer?newreg=cce6c6101cf349c58423058762fa12b2
Il met en œuvre la guillotine algorithme et exige que l'une dimension et essaie d'optimiser l'autre (vous pouvez également définir un maximum avec un petit changement dans le code). Peut-être que si vous essayez de puissance différente des deux valeurs, il va travailler pour vous.
Il n'est pas optimal, mais il est petit, portable.h seulement), et n'a aucune autre dépendance autre que le C++ et STL.