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

InformationsquelleAutor Fire Lancer | 2009-07-31