griglia ottimizzato per gli elementi rettangolari

Question

Ho Articoli N rettangolari con un rapporto di aspetto Aitem (X: Y).
Ho un'area di visualizzazione rettangolare con un rapporto di aspetto Aview

Gli articoli devono essere disposte in una disposizione di tipo tabella (cioè r righe, c colonne).

qual è la griglia ideale righe x colonne, in modo che i singoli elementi sono grande? . (Righe * colonne> = N, naturalmente - cioè non vi siano luoghi griglia "inutilizzati")

Un semplice algoritmo potrebbe iterare righe = 1..N, calcolare il numero di colonne, e mantenere la coppia riga / colonna con gli articoli più grandi.

Mi domando se c'è un algoritmo non iterativo, se (ad esempio per Aitem = Aview = 1, righe / cols può essere approssimata da sqrt (N)).

Answer 1

Nota: non riuscivo a capire la risposta di Frédéric, così ho lavorato il problema io stesso e si avvicinò con quello che sembra essere la stessa soluzione. Ho pensato che potrei anche spiegare quello che ho fatto nel caso in cui è utile.

Per prima cosa normalizzato il rapporto di aspetto della vista che degli articoli. (Sto assumendo che non si vuole ruotare gli oggetti.)

a = (view_width/view_height) / (item_width/item_height)

Ora imballaggio un rettangolo di rapporto larghezza / altezza a con quadrati è equivalente al confezionamento la vista con gli elementi. Il caso ideale sarebbe per la nostra griglia (di quadrati ora) per riempire completamente il rettangolo, che darebbe a noi

a = c/r

dove r e c sono i numeri di righe e colonne:

N = r*c

Moltiplicando / dividere queste due equazioni ci dà

N*a = c^2              N/a = r^2
c = sqrt(N*a)          r = sqrt(N/a)

Se la griglia è perfetto, r e c saranno interi, ma in caso contrario, si deve provare le tre opzioni Frédéric menzionato e mantenere quello in cui r*c è più piccola, ma ancora più di N:

• floor(r), ceil(c)
• ceil(r), floor(c)
• ceil(r), ceil(c)

Answer 2

La vostra soluzione può essere facilmente migliorata per gestire il caso generico:

Se (temporanea) dimentichiamo la necessità di avere un numero intero di righe e colonne, abbiamo

righe * colonne = N

x = AITeM * y

aview = righe * x = righe * * AITeM y

1 = colonne * y = (N / righe) * (aview / [AITeM * righe]) = N * aview / (AITeM * rows²)

dunque rows = sqrt (N * aview / AITeM) e colonne = N / righe = sqrt (N * AITeM / aview)

Poi ceil (righe) e ceil (colonne) è una soluzione che il piano (righe) e piano (colonne) sono troppo piccole per essere una soluzione insieme (se righe e colonne non sono numeri interi). Questo lascia 3 possibili soluzioni:

• Piano (righe) ceil (colonne)
• ceil (righe) del pavimento (colonne)
• ceil (righe) ceil (colonne)

a cura per correggere le equazioni. Il primo risultato è stato sbagliato (vedi commenti)

Answer 3

Buona domanda. Se la vostra vista ha dimensioni A x B (fisso) e gli oggetti hanno dimensioni A x B (variabile da massimizzare), allora avete bisogno:

trunc(A / a) * trunc(B / b) >= N

Non ho idea di come risolvere questo anche se -. Il trunc è la parte difficile, in quanto è non-lineare