Come dividere un'area composta da piccoli quadrati in rettangoli più grandi?

Question

Dove andrei a cercare algoritmi che prendono una griglia 2d di valori che sono 0 o 1 come input e quindi identificano tutti i possibili rettangoli non sovrapposti in esso?

In una spiegazione più pratica: sto disegnando una griglia che è rappresentata da un numero di quadrati e desidero trovare un modo per combinare il maggior numero possibile di quadrati adiacenti in rettangoli, al fine di ridurre il tempo trascorso in bicicletta attraverso ogni quadrato e disegnandolo.

Non è necessaria la massima efficienza, la velocità è più importante.

Addendum: Apparentemente quello che sto cercando sembra essere una tecnica chiamata Tesselation. Ora ho solo bisogno di trovare una buona descrizione per questo caso specifico.

Addendum 2: il limite di " 1 " i quadrati saranno irregolari e in alcuni casi nemmeno collegati, in quanto la distribuzione di "1" i quadrati saranno completamente casuali. Ho bisogno che queste forme irregolari siano identificate e suddivise in rettangoli regolari.

Risposta corretta: per ottenere il miglior equilibrio tra velocità ed efficienza è ottimale utilizzare i dati della griglia per riempire un albero quad con ogni nodo con un valore di stato vuoto / parzialmente riempito / riempita.

Answer 1

Ho fatto qualcosa di simile per una visualizzazione voxel veloce e sporca di scatole 3d con OpenGL.

Ho iniziato dalla casella in alto a sinistra e memorizzato il flag vuoto / pieno. Quindi ho provato ad espandere il rettangolo a destra fino a quando ho colpito una scatola con una bandiera diversa. Ho fatto lo stesso verso il basso.

Disegna il rettangolo, se è pieno.

Se sono presenti riquadri rimanenti, ripetere in modo ricorsivo la procedura per tutti e tre i rettangoli rimanenti indotti dall'ultimo rettangolo, che sono a destra, in basso e in basso a destra:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

Dai un'occhiata a questo articolo dal Portale del dottor Dobb per trovare un rettangolo massimo nella tua situazione. È una discussione molto dettagliata di un algoritmo estremamente efficiente e penso che ripeterlo ripetutamente potrebbe risolvere il tuo problema.

Answer 3

Dato che non stai cercando il numero minimo di quadrati, suggerirei di utilizzare un compromesso che mantenga comunque il tuo algoritmo semplice.

Qual è la soluzione migliore dipende dai tuoi dati, ma una semplice alternativa è semplicemente raccogliere caselle lungo una riga. Cioè:

0 0 1 1 1 0 0 0 1 1 1 1 0

Si tradurrà in:

skip 2
draw 3
skip 3
draw 4
skip 1

Questo ridurrà il numero di chiamate per disegnare la scatola senza alcuna necessità di memorizzazione nella cache (cioè puoi costruire le tue scatole al volo).

Se vuoi creare scatole più grandi, suggerirei un algoritmo di backtracking lì trovi il primo 1 e provi ad espandere il riquadro in tutte le direzioni. Crea un elenco di caselle e deseleziona 1: s come le hai utilizzate.

Answer 4

Quindi stai cercando il confine rettangolare dei quadrati 'ON'?
Vuoi il limite interno o esterno?
vale a dire. Il confine deve avere solo quadrati "ON" o vuoi che il rettangolo contenga tutti i quadrati "ON" in un gruppo?

Answer 5

Ho dovuto risolvere un problema simile, il mio algoritmo supporta array frastagliati, l'ho testato e commentato pesantemente ma è più lento del suggerimento di joel-in-g & # 246; https://stackoverflow.com/a/13802336