[ALGORITMO] Riempire un rettangolo con quadrati senza lasciare spazi vuoti

[Alhazred]

Sto realizzando una pagina web nella quale devo collocare alcune piccole immagini dentro un rettangolo.
Il rettangolo ha una larghezza fissa, ma in altezza si può adattare al contenuto, le immagini da mettere all'interno sono quadrate, ma possono essere di dimensioni qualsiasi.

Sapete se è già stato pensato un algoritmo che leggendo le dimensioni delle immagini, le ordini in modo tale che inserite in ordine all'interno del rettangolo, tra le immagini non restino spazi vuoti?

[MItaly]

Mi sono poco chiari i vincoli che dovrebbe avere questo algoritmo... le immagini all'interno sono tutti quadrati? Le loro dimensioni devono essere tutte uguali? In altre parole, quali sono i parametri (gli invarianti) dell'algoritmo e cosa dovrebbe calcolare?

[MdE2005]

Originariamente inviato da Alhazred
Sto realizzando una pagina web nella quale devo collocare alcune piccole immagini dentro un rettangolo.
Il rettangolo ha una larghezza fissa, ma in altezza si può adattare al contenuto, le immagini da mettere all'interno sono quadrate, ma possono essere di dimensioni qualsiasi.

Sapete se è già stato pensato un algoritmo che leggendo le dimensioni delle immagini, le ordini in modo tale che inserite in ordine all'interno del rettangolo, tra le immagini non restino spazi vuoti?

In questo genere di problemi è fondamentale definire la larghezza minima (l'altezza da quanto ho capito è un parametro non condizionante) di ogni immagine da inserire nel rettangolo ed un'eventuale larghezza massima.
E' inoltre opportuno spiegare meglio se l'adattamento viene riferito all'area del rettangolo o solo alla larghezza dello stesso; in quest'ultimo caso può bastare una semplice equazione di primo grado ad un'incognita.

[Alhazred]

Dunque, la larghezza del rettangolo è fissa, diciamo 960 pixel, l'altezza non è importante, si adatta al contenuto.

Le immagini da inserire nel rettangolo sono tutte quadrate, ma il lato di tali quadrati è variabile.
Ad ogni modo le immagini vengono prese da un database e una volta fatta la query sul db, so anche le dimensioni di ogni singola immagine prima di inserirla nel rettangolo.

Per farvi un'idea, dovrà venire fuori una cosa simile al sito milliondollarhomepage, sono tutte immagini quadrate e rettangolari (io però ho solo immagini quadrate) di varie dimensioni che si incastrano perfettamente, senza spazi vuoti tra una e l'altra.

[MItaly]

È il classico "packing problem", problema combinatoriale che di base avrebbe complessità non polinomiale (O(n!) o peggio), per cui approcci "stupidi" al problema (=esaminare tutte le combinazioni per trovare quella ideale) sono in genere infattibili dato il numero di combinazioni che andrebbero provate; in ogni caso, finché si tratta di rettangoli e quadrati si trovano diverse soluzioni "abbastanza ottimali", dai un'occhiata qui per un'introduzione all'argomento e qui per un algoritmo pronto. Vedi anche qui per qualche altro link sulla soluzione di problemi di questo genere.

[Alhazred]

Grazie per i link, li leggerò.

[MItaly]

[MegaAlchimista]

Comunque credo che sia impossibile (nella maggior parte dei casi) non lasciare nemmeno un pixel vuoto senza ridimensionare (magari di poco) le immagini.
Per dire: se il riquadro è largo 400, e tu hai due immagini una di 200 e l'altra di 190, l'unico modo che hai per non lasciare spazio vuoto è ridimensionare quella di 190 a 200

[MdE2005]

Originariamente inviato da MegaAlchimista
Comunque credo che sia impossibile (nella maggior parte dei casi) non lasciare nemmeno un pixel vuoto senza ridimensionare (magari di poco) le immagini.
Per dire: se il riquadro è largo 400, e tu hai due immagini una di 200 e l'altra di 190, l'unico modo che hai per non lasciare spazio vuoto è ridimensionare quella di 190 a 200

Ovvio, entro certi limiti il ridimensionamento è strettamente necessario; nella fattispecie, non essendo un problema l'altezza dell'immagine contenitore, basta risolvere la questione della larghezza delle immagini, posti dei vincoli ben precisi riguardo a larghezza massima/minima consentita e numero di immagini totali.