Suddividere un rettangolo in quasi quadrati di aree date

Question

Ne ho un set N numeri positivi e un rettangolo di dimensioni X E Y in cui devo partizionare N rettangoli più piccoli tali che:

• la superficie di ciascun rettangolo più piccolo è proporzionale al numero corrispondente nell'insieme dato
• tutto lo spazio del rettangolo grande è occupato e non c'è spazio residuo tra i rettangoli più piccoli
• ogni piccolo rettangolo dovrebbe avere la forma più vicina possibile al quadrato
• il tempo di esecuzione dovrebbe essere ragionevolmente piccolo

Ho bisogno di indicazioni a riguardo.Conoscete un algoritmo simile descritto sul web?Hai qualche idea (lo pseudo-codice va bene)?

Grazie.

Answer 1

Quello che descrivi suona come un treeMap:

I treeMaps visualizzano i dati gerarchici (strutturati all'albero) come insieme di rettangoli nidificati. A ogni ramo dell'albero viene somministrato un rettangolo, che viene quindi piastrellato con rettangoli più piccoli che rappresentano sotto-rami. Il rettangolo di un nodo foglia ha un'area proporzionale a una dimensione specificata sui dati.

Quella pagina di Wikipedia si collega a Una pagina di Ben Shneiderman, che dà una bella panoramica e collegamenti alle implementazioni Java:

Poi, mentre mi sono scontrato nel facoltà, ho avuto l'AHA! Esperienza di dividere lo schermo in rettangoli in direzioni orizzontali e verticali alternate mentre si attraversano i livelli. Questo algoritmo ricorsivo sembrava attraente, ma mi ci sono voluti alcuni giorni per convincermi che avrebbe sempre funzionato e scrivere un algoritmo a sei linee.

Wikipedia anche a "Traempaps" Treaps "di Mark Bruls, Kees Huizing e Jarke J. Van Wijk (PDF) che presenta un possibile algoritmo:

Come possiamo fare un rettangolo in modo ricorsivo in rettangoli, in modo tale che i loro aspetti (ad es. Max (altezza/larghezza, larghezza/altezza)) si avvicinano 1 il più vicino possibile? Il numero di tutte le possibili tesselazioni è molto grande. Questo problema rientra nella categoria dei problemi di NP-hard. Tuttavia, per la nostra applicazione non abbiamo bisogno della soluzione ottimale, è necessaria una buona soluzione che può essere calcolata in breve tempo.

Non si menziona alcuna ricorsione nella domanda, quindi la tua situazione potrebbe essere solo un livello del TreeMap; Ma poiché gli algoritmi funzionano a un livello alla volta, questo non dovrebbe essere un problema.

Answer 2

Ho lavorato su qualcosa di simile.Sto dando priorità alla semplicità piuttosto che ottenere proporzioni quanto più simili possibile.Questo dovrebbe (in teoria) funzionare.Testato su carta per alcuni valori di N compresi tra 1 e 10.

N = numero totale di retti da creare, q = max (larghezza, altezza) / min (larghezza, altezza), r = n / q

Se Q > N/2, dividi il rettangolo in N parti lungo il suo lato più lungo.Se Q <= N/2, dividi il rettangolo in parti R (int arrotondato) lungo il suo lato più corto.Quindi dividere i sottoretti in parti N/R (arrotondati per difetto) lungo il lato più corto.Sottrai il valore arrotondato per difetto dal risultato della successiva divisione dei subretti.Ripetere per tutti i sottoretti o fino a quando non viene creato il numero richiesto di rettilinei.