Come si ottiene l'imballaggio bidimensionale 2D a livello di programmazione?

Question

Ci sono alcune domande simili su StackOverflow, ma nessuna di queste sembra fornire una risposta tangibile che possa comprendere una persona senza una solida conoscenza dei problemi e degli algoritmi NP-hard.

Come si esegue il riempimento bidimensionale di oggetti rettangolari? Nel mio caso, sto cercando di assemblare più immagini in una singola immagine, da usare come sprite, usando la minima quantità di spazio. Ogni immagine ha probabilmente limiti molto diversi, ma non ci sono limiti per il contenitore.

Speravo che qualcuno con una comprensione degli algoritmi di impaccamento bin potesse spiegare come questo possa essere raggiunto a livello di programmazione, piuttosto che fornire una panoramica generale del metodo di imballaggio del contenitore.

Answer 1

I Googled "bin packing code" e questo è stato il mio primo successo: http://codeincomplete.com/posts/2011/5/7/bin_packing/

Ecco un riassunto: costruire un albero binario. Ogni ramo nell'albero contiene uno sprite. Ogni nodo foglia rappresenta lo spazio disponibile. Inizialmente l'albero ha solo il nodo radice, che rappresenta tutto lo spazio disponibile. Per aggiungere uno sprite all'albero, cerca nell'albero un nodo non occupato (foglia) abbastanza grande da contenere lo sprite. Trasforma quel nodo da una foglia in un ramo impostando lo sprite come occupante del nodo e dando al nodo due figli. Un bambino rappresenta lo spazio rimanente a destra dello sprite; l'altro rappresenta lo spazio rimanente sotto lo sprite e il primo figlio.

L'articolo che ho collegato sopra lo spiega molto più pienamente, con diagrammi e codice JavaScript. Spiega anche come far crescere dinamicamente il foglio sprite piuttosto che scegliere una dimensione fissa in anticipo.

Answer 2

Tutto ciò che serve è qui: https://github.com/juj/RectangleBinPack

C'è una carta e un'implementazione decente C++.

Se avete bisogno di un pseudo-codice ancora più semplice, dare un'occhiata a questo sito: http://www.blackpawn.com/texts/lightmaps/

Il "pacchetto ghigliottina" è chiamato un imballaggio albero a base di là.