partizione un rettangolo in vicino quadrati di determinate aree

Question

Ho una serie di N numeri positivi, e un rettangolo di dimensioni X e Y che ho bisogno di partizionare in N minore rettangoli tali che:

• la superficie di ciascun rettangolo più piccolo è proporzionale al suo numero corrispondente nel dato insieme
• tutto lo spazio di grande rettangolo è occupata e non c'è spazio residuo tra rettangoli più piccoli
• ogni piccolo rettangolo dovrebbe essere configurato come vicino al quadrato fattibile
• il tempo di esecuzione deve essere ragionevolmente piccola

devo indicazioni su questo. Conoscete un tale algoritmo descritto sul web? Hai qualche idea (lo pseudo-codice va bene)?

Grazie.

Answer 1

ciò che si descrive i suoni come un treemap:

Treemap visualizzare dati gerarchici (struttura ad albero) come un insieme di rettangoli nidificati. A ogni ramo dell'albero viene assegnato un rettangolo, che viene quindi affiancato da rettangoli più piccoli che rappresentano rami secondari. Il rettangolo di un nodo foglia ha un'area proporzionale a una dimensione specificata sui dati.

che Wikipedia pagina della a page by Ben Shneiderman, che dà una bella panoramica e collegamenti a implementazioni Java:

Poi mentre sconcertante su questo nel salone facoltà, ho avuto l'Aha! esperienza nel dividere lo schermo in rettangoli alternando le direzioni orizzontali e verticali mentre attraversi i livelli. Questo algoritmo ricorsivo sembrava interessante, ma mi ci sono voluti alcuni giorni per convincermi che avrebbe funzionato sempre e per scrivere un algoritmo a sei righe.

Wikipedia anche "Squarified Treemaps" by Mark Bruls, Kees Huizing and Jarke J. van Wijk (PDF) che presenta un possibile algoritmo:

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

Non si parla di ricorsione nella domanda, quindi la situazione potrebbe essere solo un livello della mappa dei tre; ma dal momento che gli algoritmi funzionano su un livello alla volta, questo non dovrebbe essere un problema.

Answer 2

Ho lavorato su qualcosa di simile. Sto dando la priorità alla semplicità rispetto all'ottenimento di proporzioni simili il più possibile. Questo dovrebbe (in teoria) funzionare. Testato su carta per alcuni valori di N tra 1 e 10.

N = numero totale di rettangoli per creare, Q = max (larghezza, altezza)/min (larghezza, altezza), R = N/Q

Se Q> N/2, dividere il rect in N parti lungo il lato più lungo. Se Q < = N/2, dividere il rettangolo in parti R (arrotondate int) lungo il lato più corto. Quindi dividere i sottobretti in N/R (arrotondato in basso int) lungo il lato più corto. Sottrarre il valore arrotondato dal risultato della successiva divisione subrects. Ripeti l'operazione per tutti i sottotitoli o finché non viene creato il numero richiesto di rects.