Programmare sistematicamente oggetti UI rettangolari in modo astratto, senza spazi vuoti

Question

Dato un insieme di 50 immagini, con diverse larghezze e altezze, come si fa a programmarle sistematicamente in modo interessante * astratto? (Vedi immagine sotto)

• Con interessante intendo, senza grandi lacune, e non facilmente righe o colonne (spazio negativo forma un sacco di intersezioni T-like) distinguibili.

Per il mio caso specifico, tutte le immagini hanno una dimensione set massimo di 150 pixel, che potrebbe significare l'altezza o larghezza è un massimo di 150 pixel (potrebbe essere 150px da 450px, 378px o 150 pixel).

Questo sembra che potrebbe essere una sfida di programmazione classica, ma mi sto trovando il tema difficile da Google ...

EDIT: Cambiato l'immagine per mostrare che non ci sono restrizioni su come la disposizione generale deve essere (non deve adattarsi all'interno di un'area specifica)

Answer 1

Il tuo problema è NP-Hard.

This thread mostra che anche con un tipo di rettangoli nXm, è NP-Hard trovare se c'è una soluzione, quindi il tuo problema più generalizzato è ovviamente anche NP-Hard [L'unico tipo di rettangolo è un caso privata di questo problema]

si potrebbe provare una soluzione backtracking se si sta dopo la soluzione, o un approccio euristico, come genetic algorithms o hill climbing, che sarà più veloce ottimizzato - ma di solito trovare un risultato non ottimale.

Answer 2

Se non si oppongono al plugin per jQuery, è possibile controllare questo fuori - http://masonry.desandro.com/

Answer 3

ho costruito qualcosa di simile a questo (anche se non è probabilmente la soluzione più sofisticata). Il mio approccio era usare un quadtree per organizzare i rettangoli che avevo posizionato sulla tela. Ho quindi semplicemente spostato il punto centrale in una spirale, provando a posizionare nuovi rettangoli e usando il quadrifoglio per rilevare le collisioni. Se avessi rilevato una collisione, avrei spostato il rettangolo che stavo cercando di posizionare sul bordo del rettangolo in cui è entrato in collisione con quello più lontano dal centro e ripetere il processo di controllo delle collisioni.

Anche in questo caso, probabilmente non è il metodo più sofisticato, e tende a lasciare spazi più ampi tra i rettangoli (i bordi tra loro non sono uniformi), ma a mio gusto ha dato buoni risultati.